1. 優(yōu)先隊(duì)列
說(shuō)堆排序之前藏杖，我們要從一種特殊的數(shù)據(jù)結(jié)構(gòu)——優(yōu)先隊(duì)列說(shuō)起黎比。
優(yōu)先隊(duì)列最大的兩個(gè)特征：插入元素和刪除最大元素
優(yōu)先隊(duì)列的實(shí)現(xiàn)方式有很多種墨闲。
我們希望插入元素和刪除最大元素的時(shí)間復(fù)雜度都能降低到最低氏涩，比如1酬诀。
| 數(shù)據(jù)結(jié)構(gòu) | 插入元素 | 刪除最大元素 |
|---|---|---|
| 有序數(shù)組 | N | 1 |
| 無(wú)序數(shù)組 | 1 | N |
| 堆 | logN | logN |
| 理想情況 | 1 | 1 |
先說(shuō)結(jié)論：用堆的方式來(lái)實(shí)現(xiàn)曹质，可以保證插入元素和刪除最大元素的時(shí)間復(fù)雜度都為logN
2. 堆
堆的定義：二叉堆婴噩，一種二叉樹(shù)的結(jié)構(gòu)，又分為大二叉堆和小二叉堆羽德，我們此處主要講大二叉堆
特點(diǎn)：二叉樹(shù)的父節(jié)點(diǎn)都大于兩個(gè)子節(jié)點(diǎn)几莽，根節(jié)點(diǎn)是二叉樹(shù)中最大的節(jié)點(diǎn)。
對(duì)于節(jié)點(diǎn)a[i]而言宅静，它的父節(jié)點(diǎn)為a[(i-1)/2]章蚣，它的子節(jié)點(diǎn)（如果有的話）為a[2i+1]和a[2i+2]
堆的兩種關(guān)鍵算法
有時(shí)，我們會(huì)發(fā)現(xiàn)有些節(jié)點(diǎn)不符合二叉堆的規(guī)則姨夹，那可以使用上浮或者下沉的算法纤垂，將元素放到合適的位置上去矾策、
上浮（針對(duì)子節(jié)點(diǎn)）
上浮算法：找到父節(jié)點(diǎn)（a[(k-1)/2]）峭沦，如果比父節(jié)點(diǎn)大贾虽，則和父節(jié)點(diǎn)交換；完成一次上浮之后吼鱼，繼續(xù)和當(dāng)前的父節(jié)點(diǎn)比較榄鉴，直到比父節(jié)點(diǎn)小為止。
代碼如下：
private void heap_swim(Comparable[] a, int k) {
while (k > 0 && less(a[(k - 1) / 2], a[k])) {
exchange(a, (k - 1) / 2, k);
k = (k - 1) / 2;
}
}
下沉（針對(duì)父節(jié)點(diǎn)）
下沉算法：找到子節(jié)點(diǎn)（a[2k+1]和a[2k+2]）中比較大的一個(gè)蛉抓，如果比子節(jié)點(diǎn)小庆尘，則和子節(jié)點(diǎn)交換；完成一次下沉后巷送，繼續(xù)與當(dāng)前的子節(jié)點(diǎn)比較驶忌，直到比子節(jié)點(diǎn)大為止。
代碼如下
private void heap_sink(Comparable[] a, int k, int n) {
while ((2 * k + 1) < n) {
int j = 2 * k + 1;
if ((j < n) && less(a[j], a[j + 1])) {
j = j + 1;
}
if (less(a[k], a[j])) {
exchange(a, k, j);
k = j;
} else {
break;
}
}
}
堆的操作
堆的初始化
堆的初始化有兩套方案：
- 順序從左到右對(duì)每個(gè)元素進(jìn)行上浮操作（把每個(gè)元素都當(dāng)成新插入的元素）笑跛。由于第1個(gè)元素（a[0]）開(kāi)始并沒(méi)有根節(jié)點(diǎn)付魔，所以，循環(huán)可以從第二個(gè)元素(a[1])開(kāi)始
for (int k = 1; k < a.length; k++){
heap_swim(a, k);
}
- 逆序從右往左對(duì)每個(gè)元素進(jìn)行下沉操作飞蹂。由于節(jié)點(diǎn)a[(n-1)/2]之后的節(jié)點(diǎn)都是子節(jié)點(diǎn)几苍，所以循環(huán)可以從a[(n-1)/2]開(kāi)始
for (int k = (n - 1) / 2; k >= 0; k--) {
heap_sink(a, k, n);
}
下沉算法的方案相對(duì)循環(huán)較少，一般堆的初始化都是采用方案二陈哑。
堆插入元素
堆的插入元素過(guò)程就是一個(gè)元素上浮的過(guò)程
堆刪除最大元素
堆的刪除最大元素分兩步：
- 將根節(jié)點(diǎn)元素與最后一個(gè)子節(jié)點(diǎn)元素交換妻坝，然后刪除最后一個(gè)節(jié)點(diǎn)，
-
根節(jié)點(diǎn)元素下沉
堆排序
前面已經(jīng)搞清楚了優(yōu)先隊(duì)列惊窖，又搞清楚了堆的結(jié)構(gòu)刽宪，以及堆的上浮和下沉算法。下面我們就來(lái)研究堆排序了界酒。
堆排序的步驟：
- 將數(shù)組中的數(shù)據(jù)初始化為二叉堆（一般使用下沉算法來(lái)實(shí)現(xiàn)）
- 取出二叉堆的根節(jié)點(diǎn)并和數(shù)組尾節(jié)點(diǎn)交換圣拄，這樣最大值就放到了a[n-1]。
- 現(xiàn)在a[0]不符合二叉堆的規(guī)則毁欣，使用下沉算法將a[0]的元素放到合適的節(jié)點(diǎn)庇谆。然后取出最大值放到a[n-2]
- 依次循環(huán)2.3步，直到所有二叉堆中所有元素取完凭疮。
private void heap_sort(Comparable[] a) {
int n = a.length - 1;
for (int k = (n - 1) / 2; k >= 0; k--) {
heap_sink(a, k, n);
}
while (n > 0) {
exchange(a, 0, n--);
heap_sink(a, 0, n);
}
}
堆排序的時(shí)間復(fù)雜度：nLgN
參考資料：《算法 第四版》
