PriorityQueue是一種抽象數(shù)據(jù)類型芭商，它表示了一組值和對這些值的操作，支持兩種操作：刪除最大元素和插入元素。它的適用場景可能是金融事務再愈，你需要從中找出最大的那些；或是農(nóng)產(chǎn)品中的殺蟲劑含量护戳，這時你需要從
中找出最小的那些翎冲， 等等

java 版的 MaxPQ 模板

public class MaxPQ <Key extends Comparable<Key>> {
    MaxPQ(Key[] a)       用 a[] 中的元素創(chuàng)建一個優(yōu)先隊列
    void insert(Key v)   向優(yōu)先隊列中插入一個元素
    Key max()            返回最大元素
    Key delMax()         刪除并返回最大元素
    boolean isEmpty()    返回隊列是否為空
    int size()           返回優(yōu)先隊列中的元素個數(shù)
}

使用二叉堆實現(xiàn)優(yōu)先隊列

二叉堆定義

二叉堆是一組能夠用堆有序的完全二叉樹排序的元素，并在數(shù)組中按照層級儲存（不使
用數(shù)組的第一個位置）

在一個堆中媳荒，位置 k 的結點的父結點的位置為k/2抗悍，而它的兩個子結點的位置則分別為 2k 和 2k+1。在排序算法中钳枕，我們只通過私有輔助函數(shù) less() 和 exch() 來訪問元素

堆.png

用它們我們將能實現(xiàn)對數(shù)級別的插入元素和刪除最大元素的操作缴渊。利用在數(shù)組中無需指針即可沿樹上下移動的便利和以下性質(zhì)，算法保證了對數(shù)復雜度的性能鱼炒。

堆的表示.png

堆的算法

我們用長度為 N+1 的私有數(shù)組 pq[] 來表示一個大小為 N 的堆疟暖，我們不會使 用 pq[0]， 堆 元 素 放 在 pq[1] 至pq[N] 中田柔。

由下至上的堆有序化（上浮 swim）

swim.png

由上至下的堆有序化（下沉 sink）

sink.png

堆的操作

插入元素: 我們將新元素加到數(shù)組末尾俐巴，增加堆的大小并讓這個新元素上浮到合適的位置

刪除最大元素: 我們從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個元素放到頂端，減小堆的大小并讓這個元素下沉到合適的位置

堆的操作.png

實現(xiàn)

public class MaxPQ<Key extends Comparable<Key>> { 
     private Key[] pq; // 基于堆的完全二叉樹
     private int N = 0; // 存儲于pq[1..N]中硬爆，pq[0]沒有使用
     
     public MaxPQ(int maxN) { 
         pq = (Key[]) new Comparable[maxN+1]; 
     }
     
     public boolean isEmpty() { 
         return N == 0; 
     }
     
     public int size() { 
         return N; 
     }
     
     // 將新元素加到數(shù)組末尾欣舵，增加堆的大小并讓這個新元素上浮到合適的位置
     public void insert(Key v) { 
         pq[++N] = v; 
         swim(N); 
     }
     
     // 從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個元素放到頂端，減小堆的大小并讓這個元素下沉到合適的位置
     public Key delMax() {
         Key max = pq[1];  // 從根結點得到最大元素
         exch(1, N--);     // 將其和最后一個結點交換
         pq[N+1] = null;   // 防止對象游離
         sink(1);          // 恢復堆的有序性
         return max; 
     }
     
     private void swim(int k) {
         while (k > 1 && less(k/2, k)) { 
             exch(k/2, k); 
             k = k/2;  // java 中向下取整
         }
     }
     
     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; 
         }
     }
     
    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; 
    }
 
}

堆排序

public static void sort(Comparable[] a) { 
    int N = a.length; 
    
    for (int k = N/2; k >= 1; k--) { // for 循環(huán)構造了堆
        sink(a, k, N); 
    }
 
    while (N > 1) { // while 循環(huán)將最大的元素 a[1] 和 a[N] 交換并修復了堆缀磕，如此重復直到堆變空缘圈。
       exch(a, 1, N--); 
       sink(a, 1, N); 
    } 
}

堆的構造和下沉排序.png

小結

堆排序在排序復雜性的研究中有著重要的地位劣光，因為它是我們所知的唯一能夠同時最優(yōu)地利用空間和時間的方法——在最壞的情況下它也能保證使用～ 2NlgN 次比較和恒定的額外空間。

當空間十分緊張的時候（例如在嵌入式系統(tǒng)或低成本的移動設備中）它很流行糟把，因為它只用幾行就能實現(xiàn)（甚至機器碼也是）較好的性能绢涡。但現(xiàn)代系統(tǒng)的許多應用很少使用它，因為它無法利用緩存遣疯。數(shù)組元素很少和相鄰的其他元素進行比較雄可，因此緩存未命中的次數(shù)要遠遠高于大多數(shù)比較都在相鄰元素間進行的算法，如快速排序缠犀、歸并排序数苫，甚至是希爾排序。