二叉堆其實就是一棵堆有序的二叉樹
開篇
本篇文章主要講什么
此文是排序算法系列文章的倒數(shù)第三篇，因此本文的主要意圖還是講排序算法，這次我們一起聊聊堆排序。
在正式開始之前，我們先要花些篇幅聊兩種很重要的基礎數(shù)據(jù)結(jié)構(gòu)——優(yōu)先隊列和二叉堆。
正文
優(yōu)先隊列（PriorityQueue）
有時我們需要處理一組有序數(shù)據(jù)時，并不需要它們整體有序。設想這樣一種情況，對于一組數(shù)據(jù)，每次我們都只處理其中鍵值最大的元素，我們可能會把這組數(shù)據(jù)的規(guī)模擴大，往里面放更多新元素，但仍是每次挑鍵值最大的元素來處理。對于這種情況我們當然可以使整組數(shù)據(jù)一直保持整體有序，但這不是必要的——我們只需保證第一個元素始終是鍵值最大那個就行。
這就需要引入了一種新的數(shù)據(jù)結(jié)構(gòu)——優(yōu)先隊列，它應該高效地實現(xiàn)兩種基本操作，訪問最大元素和插入元素。
一種優(yōu)先隊列的經(jīng)典實現(xiàn)方式就是使用二叉堆這種更低級點的數(shù)據(jù)結(jié)構(gòu)。
二叉堆（BinaryHeap）
接著來詳細了解下二叉堆（下簡稱堆）這種數(shù)據(jù)結(jié)構(gòu)。
看到這個名字你是不是想到了二叉樹？堆其實就是一棵堆有序的二叉樹（二叉樹這種更低級的數(shù)據(jù)結(jié)構(gòu)非本文重點，此處略過不表，還請讀者自行復習二叉樹相關(guān)知識）。
何為堆有序？
當一顆二叉樹的每個結(jié)點其鍵值都大于等于它的兩個子結(jié)點時，我們稱其是堆有序的。
也即在一顆堆有序的二叉樹中，每個結(jié)點的鍵值都小于等于它的父結(jié)點。很容易確定，根結(jié)點是一棵堆有序的二叉樹中鍵值最大的結(jié)點。
這是一個堆：
11
/ \
9 10
/ \ / \
5 6 7 8
/ \ / \
1 2 3 4
具體我們?nèi)绾卧诔绦蛑斜硎疽粋€堆呢？用數(shù)組即可。
就是將堆（二叉樹）的結(jié)點按層級順序依次放入數(shù)組中。為了方便后面算法的表示，我們不使用數(shù)組的第一個位置，即從數(shù)組下標為 1 的位置開始存儲一個堆。把上面的堆放入數(shù)組中我們可以得到：
[-1，11, 9, 10, 5, 6, 7, 8, 1, 2, 3, 4]//把上面的二叉堆按層級順序放入數(shù)組中，注意我們沒使用數(shù)組第一個位置，我們把沒使用到的數(shù)組位置置值為-1表示
這樣一個數(shù)組。
這樣表示的堆有幾條重要性質(zhì)：
- 位置（也即下標） n 的結(jié)點其父結(jié)點的位置為 n/2
- 位置（也即下標） n 的結(jié)點其兩個子結(jié)點的位置為 2n 或 2n + 1（如果兩個子結(jié)點都存在的話）
- 一顆大小為 N 的完全二叉樹其高度為（lg N)
1 和 2 讓我們可以不使用指針，僅通過計算數(shù)組的索引在樹中上下移動，3 保證了我們實現(xiàn)的基本操作其算法僅具有對數(shù)級別的時間復雜度。
下面我們用 Java 代碼來實現(xiàn)一個基于二叉堆的自然數(shù)優(yōu)先隊列：
/**
* 基于二叉堆實現(xiàn)的正整數(shù)優(yōu)先隊列
* 注意下面注釋的表述可粗略認為優(yōu)先隊列等于二叉堆等于二叉樹
*/
public class IntPQ {
private int[] heap;//用于存放整個二叉堆(值)的數(shù)組，不使用數(shù)組第一個位置，即 heap[0] 我們永遠也用不到
private int size = 0;//堆當前的體積大小，二叉堆存儲于數(shù)組 heap 的[1-size] 中，heap[0] 無用
/**
* <p>構(gòu)造函數(shù)</p>
* @param size：需要構(gòu)造的優(yōu)先隊列的初始大小
*/
public IntPQ(int size) {
heap = new int[size + 1];
}
/**
* <p>交換數(shù)組中兩個位置的值</p>
* @param i 待交換值的位置
* @param j 待交換值的位置
*/
private void exch(int i, int j){
if (i < 1 || i >= heap.length || j < 1 || j >= heap.length){
return;
}
int mid = heap[i];
heap[i] = heap[j];
heap[j] = mid;
}
/**
*
* @return 優(yōu)先隊列是否是空的
*/
public boolean isEmpty(){
return size == 0;
}
/**
*
* @return 優(yōu)先隊列當前大小
*/
public int size(){
return size;
}
/**
* 注意下面兩個方法極為重要，即二叉堆結(jié)點的躍遷和降級操作，
* 什么意思呢？
* 首先我們要知道數(shù)據(jù)結(jié)構(gòu)的樹和現(xiàn)實世界中的樹有點不一樣，數(shù)據(jù)結(jié)構(gòu)的樹樹根在上樹葉在下，現(xiàn)實世界反之，我們這里討論數(shù)據(jù)結(jié)構(gòu)的樹
* 所謂躍遷操作，就是這個樹下面的某個結(jié)點的鍵值比它的父結(jié)點要大，那它肯定要躍遷到它父結(jié)點上面才能使整棵樹堆有序
* 反之，就是所謂的降級操作
* 就是堆中某個結(jié)點不在它該在的位置，打破了二叉樹的堆有序時，我們將其歸位讓二叉樹重新堆有序的操作
* 這兩個方法是 insert 和 delMax 方法的基礎*/
/**
* <p>二叉堆中指定位置結(jié)點的躍遷操作，如果此結(jié)點的值比它的父結(jié)點大，就和父結(jié)點交換位置，如此往復直至樹的根部</p>
* @param i 待躍遷結(jié)點位置
*/
private void up(int i){
while (i > 1 && heap[i] > heap[i/2]){//需要上浮的結(jié)點位置在根結(jié)點下面且值大于它的父結(jié)點
//交換 i 和 i/2 兩個位置的值
exch(i, i/2);
i /= 2;
}
}
/**
* <p>二叉堆中指定位置結(jié)點的降級操作，如果此結(jié)點的值比它的兩個自結(jié)點中較大那個小，就和此子結(jié)點交換位置，如此往復直至樹的葉子結(jié)點那層</p>
* @param i 待躍遷結(jié)點位置
*/
private void down(int i){
while (i * 2 <= size){
int j = i * 2;
if (j < size && heap[j] < heap[j + 1]){
j += 1;
}
if (heap[i] < heap[j]){
//交換 i 和 j 兩個位置的值
exch(i, j);
i = j;
}else {
break;
}
}
}
/**
* <p>結(jié)點插入操作，注意這里我偷懶沒寫給數(shù)組擴容的邏輯，因這不是重點略過沒寫，讀者可自行改進
* 此方法具有對數(shù)級別的平均時間復雜度</p>
* @param value 待插入的結(jié)點
*/
public void insert(int value){
//將結(jié)點插入當前二叉樹的最后面，同時使當前二叉樹的大小加一
heap[++ size] = value;
//新插入的結(jié)點可能會破壞二叉樹的堆有序，然后對其執(zhí)行躍遷操作，以讓其歸入正確位置，確保二叉樹的堆有序
up(size);
}
/**
* <p>刪除并返回隊列中值最大的那個元素（其實就是當前樹根），也就是樹根結(jié)點，此方法具有對數(shù)級別的平均時間復雜度</p>
* @return
*/
public int delMax(){
int max = heap[1];//從二叉樹的根結(jié)點得到鍵值最大的元素
//將根結(jié)點的最后一個葉子結(jié)點交換位置，并將樹的大小減一，
// 此時我們相當于把根結(jié)點刪除了，但新的根結(jié)點鍵值不一定是最大的，
// 所以我們需要降級歸位，使二叉樹重新堆有序
exch(1, size --);
down(1);//根結(jié)點降級歸位，使二叉樹重新堆有序
return max;
}
}
堆排序
經(jīng)過上面那么多鋪墊，一種新的排序算法已呼之欲出。
是滴，利用二叉堆這種數(shù)據(jù)結(jié)構(gòu)，我們可以實現(xiàn)一種新的排序算法——堆排序。
終于說到堆排序了！你可以暫緩幾分鐘，接著我們來好好聊聊什么是堆排序，準備好~
堆排序的思路是這樣的，利用優(yōu)先隊列（基于二叉堆）的兩個基本操作（插入元素和刪除最大元素），我們可以寫出對數(shù)組原地排序的更高效算法，其最壞時間復雜度僅為線性對數(shù)級別的（n log n）。具體算法實現(xiàn)共分兩步，構(gòu)造堆和銷毀堆。
- 構(gòu)造堆：即先對數(shù)組進行原地調(diào)整，讓整個數(shù)組堆化?；诙言氐能S遷和降級操作，你或許會有多種思路來將一個數(shù)組堆化，這里我們使用一種最經(jīng)典高效的方法來將一個數(shù)組堆化。即使用下沉操作遍歷樹中的所有非葉子結(jié)點，遞歸地給數(shù)組構(gòu)造出堆的秩序。為什么要這樣來構(gòu)造堆？因為這是對數(shù)組操作最少，最節(jié)省成本的堆構(gòu)造方式。這個問題其實很有意思，值得好好思考。之所以只遍歷所有非葉子結(jié)點，是因為我們可以跳過所有大小為 1 的子堆，因為大小為 1 的子堆（子樹）已經(jīng)是一個堆了（已經(jīng)堆有序了），而如果一個結(jié)點的兩個子結(jié)點已經(jīng)是堆了，那在此結(jié)點上調(diào)用降級操作可將它們變成一個整體的堆，就是如此，遞歸地給數(shù)組建立起堆的秩序。這里有個問題，堆中的非葉子結(jié)點分布在數(shù)組中的什么位置區(qū)間？如果現(xiàn)在的數(shù)組規(guī)模為 n ，那答案就是從堆第一個結(jié)點的位置到數(shù)組下標 n/2，即[1, n/2]，這點很容易自證。如果用來給數(shù)組原地排序的話，那堆在數(shù)組中存放時就不能跳過第一個位置了，這樣當前堆所有非葉子結(jié)點所在區(qū)間就是[0, n/2 - 1]。
- 銷毀堆：將數(shù)組構(gòu)建出堆秩序后，我們已經(jīng)得到了一個堆。再進一步，使數(shù)組達到整體有序，接下來要做的就是一個結(jié)點一個結(jié)點地銷毀掉整個堆。你應該很容易想到，所用方法正是遞歸地刪除當前二叉堆的樹根，將其跟最后一個結(jié)點交換位置，然后堆的規(guī)模減一，此時新的根結(jié)點可能會破壞堆有序狀態(tài)，我們對其進行降級操作使新的規(guī)?？s減的堆重新變成堆有序，如此遞歸，直至堆的規(guī)?？s減為一，此時整個數(shù)組達到整體有序，排序完成。
OK 捋完整體邏輯我們來擼一下代碼：
/**
* <p>堆排序的 Java 實現(xiàn)</p>
* @param array: 待排序數(shù)組，我們采用原地排序
*/
public static void sortHeap(int[] array){
//第一步，構(gòu)建堆
int start = array.length/2 - 1;//構(gòu)建堆的開始遍歷下標，因為數(shù)組是從下標 0 開始存放堆的，所以減一，此下標在遍歷中遞減
int bound = array.length - 1;//待操作子堆最后一個下標，也可看做當前堆長度，不過此長度從 0 開始計
for (; start >= 0; start --){
down(array, start, bound);
}
//第二步，銷毀堆，這個過程跟選擇排序有點類似
while (bound > 0){
exch(array, 0, bound);
down(array, 0, -- bound);
}
}
/**
* <p>交換數(shù)組中兩個位置的值</p>
* @param i 待交換值的位置
* @param j 待交換值的位置
*/
private static void exch(int[] array, int i, int j){
if (i < 0 || i >= array.length || j < 0 || j >= array.length){
return;
}
int mid = array[i];
array[i] = array[j];
array[j] = mid;
}
/**
* <p>調(diào)整后的堆結(jié)點降級操作</p>
* @param heap 待操作數(shù)組，存放堆
* @param index 待降級操作的結(jié)點位置
* @param bound 待操作結(jié)點所在子堆(此子堆根結(jié)點目前不在應在位置，我們對其根結(jié)點執(zhí)行降級操作使其歸位)的最后一個結(jié)點位置（下標）
*/
private static void down(int[] heap, int index, int bound){
//注意對比原始的 down 方法中操作下標的地方，這里多了很多 + 1 操作，原因就是我們從數(shù)組中第一個位置開始存放堆
while (index * 2 + 1 <= bound){
int j = index * 2 + 1;
if (j < bound && heap[j] < heap[j + 1]){
j += 1;
}
if (heap[index] < heap[j]){
//交換 i 和 j 兩個位置的值
exch(heap, index, j);
index = j;
}else {
break;
}
}
}
代碼主要看 sortHeap 方法。
我的天花這么多篇幅終于聊完本文主角堆排序了！
總結(jié)
堆排序的效率比 冒泡排序、選擇排序、插入排序和希爾排序都要高，其最差時間復雜度僅為線性對數(shù)級別的O(n log n)。
尾巴
關(guān)于優(yōu)先隊列這種數(shù)據(jù)結(jié)構(gòu)，它的應用場景可不止排序，本系列后續(xù)文章會再單獨聊聊這種數(shù)據(jù)結(jié)構(gòu)，你會看到更多優(yōu)先隊列大顯身手的應用場景，敬請期待。
下篇，我們聊聊歸并排序。
完。
