Java中基于堆的最小堆实现

Java中的java.util包提供了一个基于堆的最小堆实现，称为PriorityQueue。本文将介绍PriorityQueue的基本原理、实现和使用方法。

堆的基本原理

堆是一种特殊的二树，满足以下两个条件：

1. 节点的值小于或等于子节点的值（最小堆）或父节点的值大于或等于子节点的值（最大堆）。
2. 堆是一棵完全二叉树，即除了最后一层外，所有层都是满的。

最小堆的实现

PriorityQueue类使用一个数组来存储元素，并使用堆的性质来维护最小堆。堆的基本操作包括：

1. add(E element): 添加一个元素到堆中。
2. poll(): 删除并返回堆中最小的元素。
3. peek(): 返回堆中最小的元素，但不删除它。

Java中最小堆的实现

PriorityQueue类使用一个数组queue来存储元素，并使用两个指针size和modCount来维护堆的大小和修改次数。

public class PriorityQueue<E> {
    private final Object[] queue;
    private int size;
    private int modCount;

    public PriorityQueue(int initialCapacity) {
        queue = new Object[initialCapacity];
    }

    public boolean add(E element) {
        // 添加元素到堆中
        queue[size++] = element;
        // 维护堆的性质
        heapifyUp(size - 1);
        return true;
    }

    public E poll() {
        // 删除并返回堆中最小的元素
        E result = (E) queue[0];
        queue[0] = queue[--size];
        // 维护堆的性质
        heapifyDown(0);
        return result;
    }

    public E peek() {
        // 返回堆中最小的元素，但不删除它
        return (E) queue[0];
    }

    private void heapifyUp(int index) {
        // 维护堆的性质
        while (index > 0) {
            int parentIndex = (index - 1) / 2;
            if (compare(queue[parentIndex], queue[index]) <= 0) {
                break;
            }
            swap(parentIndex, index);
            index = parentIndex;
        }
    }

    private void heapifyDown(int index) {
        // 维护堆的性质
        while (true) {
            int leftChildIndex = 2 * index + 1;
            int rightChildIndex = 2 * index + 2;
            int smallest = index;
            if (leftChildIndex < size && compare(queue[leftChildIndex], queue[smallest]) < 0) {
                smallest = leftChildIndex;
            }
            if (rightChildIndex < size && compare(queue[rightChildIndex], queue[smallest]) < 0) {
                smallest = rightChildIndex;
            }
            if (smallest == index) {
                break;
            }
            swap(smallest, index);
            index = smallest;
        }
    }

    private void swap(int i, int j) {
        // 交换两个元素
        Object temp = queue[i];
        queue[i] = queue[j];
        queue[j] = temp;
    }

    private int compare(Object o1, Object o2) {
        // 比较两个元素
        return ((Comparable) o1).compareTo(o2);
    }
}

使用方法

PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.add(5);
queue.add(2);
queue.add(8);
queue.add(3);
System.out.println(queue.poll()); // 2
System.out.println(queue.poll()); // 3
System.out.println(queue.poll()); // 5
System.out.println(queue.poll()); // 8

结论

Java中的PriorityQueue类提供了一个基于堆的最小堆实现，可以方便地实现优先级队列和堆排序等功能。本文介绍了PriorityQueue的基本原理、实现和使用方法，希望对读者有所帮助。