\(13.3\)优先队列的实现

(注：这里实现的是大根堆)

1.优先队列的初始化

public class MaxPQ<Key extends Comparable<Key>> 
{
    private Key[] pq; // heap-ordered complete binary tree
    private int N = 0; // in pq[1..N] with pq[0] unused
    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]; // Retrieve max key from top.
        swap(1, N--); // Exchange with last item.
        pq[N+1] = null; // Avoid loitering.
        sink(1); // Restore heap property.
        return max;
    }

    private boolean less(int i, int j);
    private void swap(int i, int j);
    private void swim(int k);
    private void sink(int k);
}

2.辅助方法的实现

  \(a.\)less、swap方法

private boolean less(int i, int j) {
    return pq[i].compareTo(pq[j]) < 0;
}

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

  \(b.\)swim方法

  swim方法用于将堆底部的元素向上洄游，以维护堆的性质：

private void swim(int k) {
    while (k > 1 && less(k / 2, k)) {
        swap(k / 2, k);
        k = k / 2;
    }
}

  \(c.\)sink方法

  sink方法用于将堆顶部的元素下沉，以维护堆的性质：

private void sink(int k) {
    while (2 * k <= N) {
        int j = 2 * k;
        //assure that the parent is the biggest of its children
        if (j < N && less(j, j + 1)) {
            swap (j, j + 1);
        }
        if (!less(k, j)) {
            break;
        }
        swap (k, j);
        k = j;
    }
}