算法2.6 基于堆的优先队列

  1. public class MaxPQ<Key extends Comparable<Key>> {
  2.     private Key[] pq;
  3.     private int N = 0;
  5.     public MaxPQ(int maxN){
  6.         pq = (Key[])new Comparable[maxN+1];//pq[0]未使用,数组容量加一
  7.     }
  9.     public boolean isEmpty(){ return N == 0;}
  10.     public int size(){ return N;}
  12.     public void insert(Key v){
  13.         if(N == pq.length - 1) resize(2*pq.length);
  14.         pq[++N] = v;
  15.         swim(N);
  16.     }
  18.     private boolean less(int i, int j){
  19.         return pq[i].compareTo(pq[j]) < 0;
  20.     }
  21.     private void exch(int i, int j){
  22.         Key temp = pq[i];
  23.         pq[i] = pq[j];
  24.         pq[j] = temp;
  25.     }
  27.     private void swim(int k){
  28.         while (k > 1 && less(k/2, k)){
  29.             exch(k, k/2);
  30.             k = k/2;
  31.         }
  32.     }
  34.     private void sink(int k){
  35.         while (k*2 <= N){
  36.             int j = k*2;
  37.             if (less(j, j+1) && j < N) j++;//取子结点较大者;j<N,取等号j++溢出
  38.             if (! less(k,j)) break;//比较父子大小
  39.             exch(k,j);
  40.             k = j;
  41.         }
  42.     }
  44.     private Key delMax(){
  45.         Key max = pq[1];
  46.         exch(1,N--);
  47.         pq[N+1] = null;//防止对象游离
  48.         if((N > 0)&&(N <= pq.length/4)) resize(pq.length/2);
  49.         sink(1);//恢复有序
  50.         return max;
  51.     }
  53.     private void resize(int size){
  54.         if (size <= N) return;
  55.         Key[] temp = (Key[])new Comparable[size];
  56.         for (int i = 1; i <= N; i++){
  57.             temp[i] = pq[i];
  58.         }
  59.         pq = temp;
  60.     }
  61. }

算法分析

  1. //插入
  2. private void insert(Key v){
  3.     pq[++N] = v;
  4.     swim(N);
  5. }
  7. //删除最大元素
  8. private Key delMax(){
  9.     Key max = pq[1];
  10.     exch(1,N--);
  11.     pq[N+1] = null;//防止对象游离
  12.     sink(1);//恢复有序
  13.     return max;
  14. }
  16. //上浮
  17. private void swim(int k){
  18.     while (k > 1 && less(k/2, k)){
  19.         exch(k, k/2);
  20.         k = k/2;
  21.     }
  22. }
  24. //下沉
  25. private void sink(int k){
  26.     while (k*2 <= N){
  27.         int j = k*2;
  28.         if (less(j, j+1) && j < N) j++;//取子结点较大者;j<N,取等号j++溢出
  29.         if (! less(k,j)) break;//比较父子大小
  30.         exch(k,j);
  31.         k = j;
  32.     }
  33. }

对于一个含有N个元素的基于堆的队列,插入元素操作需要比较次数(less())不超过(lgN+1)次,删除最大元素操作需要不超过2lgN次操作

证明:已知两种操作都是需要在根结点和堆底移动元素,且路径长度不超过lgN.

  • 对于insert(),当插入的第(N+1)个元素最大,上浮到根结点需要不超过(lgN+1)次比较;
  • 对于delMax(),除了堆底元素,删除最大元素都需要先比较找出较大子结点,再比较父子结点确定是否上浮,总共不超过2lgN次比较.

要点

  1. pq[0]未使用,传入大小maxN,实际创建出大小(maxN+1)的数组
  2. delMax()中需要pq[N+1]=null防止对象游离