二叉堆实现优先队列_c++实现二叉堆优先队列

优先队列支持两种操作：删除最大(小)元素和插入元素。

public class MaxPQ<Key extends Comparable<Key>> {

    private Key[] pq;
    private int N = 0;

    public MaxPQ(int maxN) {
        pq = (Key[]) new Comparable[maxN + 1];
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public int size() {
        return N;
    }

    public void insert(Key v) {
        //将新元素添加到数组尾
        pq[++N] = v;
        //恢复堆的有序性
        swim(N);
    }

    public Key delMax() {
        //从根节点得到最大元素
        Key max = pq[1];
        //将其和最后一个节点交换
        exch(1, N--);
        //防止对象游离
        pq[N+1] = null;
        //恢复堆的有序性
        sink(1);
        return max;
    }
    private boolean less(int i , int j) {
        return pq[i].compareTo(pq[j]) < 0;
    }

    private void exch(int i, int j) {
        Key t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }

    /**
     * 上浮操作
     * 如果堆的有序状态由于某个结点变得比它的父结点更大而被打破，那么我们就需要通过交换它和它的父结点来修复堆。
     * 交换后，这个结点比它的两个子结点都大（一个是曾经的父结点，另一个比它小，因为其是父结点的子结点），但是这个结点仍然可能比它现在的父结点大，因为需要用同样的方法恢复秩序，
     * 将这个结点不断上移直到遇到一个更大的父结点。
     * @param k
     */
    private void swim(int k) {
        while(k > 1 && less(k/2, k)) {
            exch(k/2, k);
            k = k/2;
        }
    }

    /**
     * 下沉操作
     * 如果堆的有序状态是由于某个结点比它的两个子结点或比其中之一更小而被打破，那么就可以通过将它和它的两个子结点中较大者交换来恢复堆。
     * 交换后的堆有序状态可能依然被打破，需要继续重复上述操作，直到该结点到达一个位置，在该位置时，它的值不小于它的两个子结点或者到达堆底部。
     * @param k
     */
    private void sink(int k){
        while(2*k <= N) {
            int j = 2*k;
            //找到左右结点中值最大的那个结点
            if(j < N && less(j, j+1))
                j++;
            if(!less(k, j))
                break;
            exch(k,j);
            k = j;
        }
    }
}