二叉堆实现优先队列

最大堆：

每个节点都大于等于它的两个子节点

堆的操作：

swim(k)：上浮第k个元素sink(k)：下沉第k个元素

优先队列

删除：delMax（最小堆delMin）插入：insert

代码框架

public class MaxPQ <Key extends Comparable<Key>> { // 存储元素的数组 private Key[] pq; // 当前 Priority Queue 中的元素个数 private int N = 0; public MaxPQ(int cap) { // 索引 0 不用，所以多分配一个空间 pq = (Key[]) new Comparable[cap + 1]; } /* 返回当前队列中最大元素 */ public Key max() { return pq[1]; } /* 插入元素 e */ public void insert(Key e) {...} /* 删除并返回当前队列中最大元素 */ public Key delMax() {...} /* 上浮第 k 个元素，以维护最大堆性质 */ private void swim(int k) {...} /* 下沉第 k 个元素，以维护最大堆性质 */ private void sink(int k) {...} /* 交换数组的两个元素 */ private void exch(int i, int j) { Key temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; } /* pq[i] 是否比 pq[j] 小？ */ private boolean less(int i, int j) { return pq[i].compareTo(pq[j]) < 0; } /* 还有 left, right, parent 三个方法 */ }

实现swim

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

实现sink

private void sink(int k) { while(left(k) <= N) { // 找出最大的孩子节点 int child = left(k); if(right(k) <= N && less(child, right(k))) child = right(k); if(less(child, k)) break; exch(k, child); k = child; } }

实现删除

private Key delMax() { int del = pq[1]; exch(1, N); pq[N] = null; N--; sink(1); return del; }

实现插入

private void insert(Key e) { N++; pq[N] = e; swim(N); return; }