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() 來訪問元素
用它們我們將能實現(xiàn)對數(shù)級別的插入元素和刪除最大元素的操作缴渊。利用在數(shù)組中無需指針即可沿樹上下移動的便利和以下性質(zhì),算法保證了對數(shù)復雜度的性能鱼炒。
堆的算法
我們用長度為 N+1 的私有數(shù)組 pq[] 來表示一個大小為 N 的堆疟暖,我們不會使 用 pq[0], 堆 元 素 放 在 pq[1] 至pq[N] 中田柔。
由下至上的堆有序化(上浮 swim)
由上至下的堆有序化(下沉 sink)
堆的操作
插入元素: 我們將新元素加到數(shù)組末尾俐巴,增加堆的大小并讓這個新元素上浮到合適的位置
刪除最大元素: 我們從數(shù)組頂端刪去最大的元素并將數(shù)組的最后一個元素放到頂端,減小堆的大小并讓這個元素下沉到合適的位置
實現(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);
}
}
小結
堆排序在排序復雜性的研究中有著重要的地位劣光,因為它是我們所知的唯一能夠同時最優(yōu)地利用空間和時間的方法——在最壞的情況下它也能保證使用~ 2NlgN 次比較和恒定的額外空間。
當空間十分緊張的時候(例如在嵌入式系統(tǒng)或低成本的移動設備中)它很流行糟把,因為它只用幾行就能實現(xiàn)(甚至機器碼也是)較好的性能绢涡。但現(xiàn)代系統(tǒng)的許多應用很少使用它,因為它無法利用緩存遣疯。數(shù)組元素很少和相鄰的其他元素進行比較雄可,因此緩存未命中的次數(shù)要遠遠高于大多數(shù)比較都在相鄰元素間進行的算法,如快速排序缠犀、歸并排序数苫,甚至是希爾排序。