# 《Algorithms算法》笔记：优先队列(2)——二叉堆

2016-04-29

## 4 二叉堆优先队列代码

``````/**
*
* @author rocky
*/
public class MaxPQ> {

private Key[] pq;
private int N;

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

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

public void insert(Key key)
{
N++;
pq[N] = key;
swim(N);
}

public Key delMax() {
Key max = pq[1];  //get the max element
exch(1, N);     //exchange between the root and the last element
N--;
sink(1);   //sink to the right place
pq[N+1] = null;   //delete
return max;
}

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

}

private void sink(int k) {
while(k*2 <= N)    //if this node has left child
{
int child = k * 2;
if (child < N && less(child, child + 1)) {  //if the left child is less than the right child
child = child + 1;   //change child to the right child
}
if (less(k, child)) {
exch(k, child);
}
k = child;
}
}

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;
}
}
``````