搞懂二叉堆的那些事
1. 什么是二叉堆?
“二叉”自不必多說，本章主要介紹的樹都是二叉樹。那么啥是“堆”呢?
我們在日常生活中，通常會說“一堆東西”或者“堆東西”，這里的“堆”，通常指重疊放置的許多東西。
一堆東西
我們在堆東西的時候，肯定都有一個經驗，即：為了使這堆東西更穩定，會將比較重的、大的東西放在下面，比較輕的、小的東西放在上面。
這個經驗放在數據結構——二叉樹中，同樣適用。只不過“重”“大”是根據結點值的大小來判斷的，并且是在雙親結點和孩子結點之間進行比較的。
比如，結點值大的，作為孩子結點;結點值小的，作為雙親結點。
下面舉一個例子，先看下面一顆普通二叉樹，也是一顆完全二叉樹：
再看下面一顆二叉堆：
最小堆
這個二叉堆的特點是：
- 它是一顆完全二叉樹。事實上，該二叉堆就是由上圖的完全二叉樹經過調整轉化而來;
- 任何一個雙親結點的值，均小于或等于左孩子和右孩子的值;
- 每條分支從根結點開始都是升序排序(如分支 1-2-3-4)。
這樣的二叉堆被稱為最小堆，它的堆頂，即根結點 A，是整棵樹的最小值。
與最小堆相對應的是最大堆：
- 最大堆是一顆完全二叉樹;
- 它的任何一個雙親結點的值，均大于或等于左孩子和右孩子的值;
- 每條分支從根結點開始都是降序排序。
最大堆的堆頂，是整棵樹的最大值。
我們將上圖中的普通二叉樹轉化為最大堆，如下圖：
最大堆
2. 二叉堆的操作
2.1. 構造二叉堆
給你一顆完全二叉樹，如何調整結點，構造出一個二叉堆?下面是一顆無序的完全二叉樹：
現在我們想要構造出一個最小堆，首先找到這顆完全二叉樹中所有的非葉子結點(綠色標記)：
我們要做的事是：對每個非葉子結點，做最小堆的“下沉”調整。
何謂最小堆的“下沉”調整?
對某個非葉子結點，如果該結點大于其孩子結點中最小的那個，則交換二者位置，否則不用交換。在圖上則表現出非葉子結點(即大值結點)“下沉”一個層次。運動是相對的，大值結點“下沉”，就相當于小值結點“上浮”。
需要注意的是，有時下沉一次是不夠的，我們需要下沉多次，確保該結點下沉到底(即它不再大于其孩子)。
所有非葉子結點，從最后一個開始，按照從右到左，從下到上的順序進行多次最小堆的下沉調整，即可構造成最小堆。
比如對于值為 4 的非葉子結點而言，它下沉到第 3 層次后，仍然大于其孩子，這不算“下沉到底”，還需要繼續下沉到第 4 層次。至此，在分支 2-4-3-1 上，“大值”結點 4 算是下沉到底了。
下面進行分步解釋：
1.對非葉子結點 7，它小于其孩子結點 10， 不用“下沉”;
2.對非葉子結點 3，它大于其孩子結點中較大的結點 1，結點 3 要“下沉”，和結點 1 交換。顯然，結點 3 沉到底了。
3.對非葉子結點 6，它大于其孩子結點中較小的結點 5，結點 6 要“下沉”， 和結點 5 交換位置。顯然，結點 6 沉到底了。
4.對非葉子結點 4，它大于其孩子結點中最小的結點 1，結點 4 要 “下沉”，和結點 1 交換位置。顯然，結點 4 并未沉到底。
5.仍對結點 4，它大于其孩子結點中最小的結點 3，結點 4 要“下沉”， 和結點 3 交換位置。此時，結點 4 算是沉底了。
6.對非葉子結點 2，它大于其孩子結點中最小的結點 1，結點 2 要“下沉”，和結點 1 交換位置。顯然，結點 2 算是沉到底了。
至此，我們將一顆無序的完全二叉樹調整改造成了最小二叉堆，你可以檢查一下，最小堆中的所有結點皆滿足雙親的值小于孩子的值。并且，5 條分支上都是有序的。
構造最大堆的步驟類似，不過最大堆的下沉調整是：如果某結點小于其孩子結點中最大的那個，則交換二者位置，在圖上表現為非葉子結點(即小值結點)“下沉”一個層次。通過多次下沉調整，使該結點不再小于其孩子。
下圖把一個無序完全二叉樹調成為最大堆：
2.2. 插入結點
二叉堆是一個完全二叉樹，要向其中插入結點，插入到完全二叉樹的最后一個結點的下一個位置即可。
比如向下面的一個最大堆中插入結點 11，要插到最后一個結點 4 的下一個位置。當最大堆新插入一個結點 11 時，它就不再是最大堆了，因為結點 11 破壞了原堆的結構。所以，我們應當將其看作一個新的完全二叉樹，然后調整新完全二叉樹再次構造出最大堆。(調整過程見上)
插入過程
2.3. 刪除結點
刪除操作與插入操作相反，是刪除第一個位置的元素，即刪除堆頂。
我們以刪除上圖最大堆的堆頂 11 為例。
當刪除堆頂 11 后，二叉堆原結構被破壞，甚至不是一顆二叉樹了(變成兩顆)：
為了保持完全二叉樹的形態，我們把最后一個結點 7 補到根結點去，頂替被刪除的根結點 11。如此一來，我們又得到了一個新完全二叉樹(不是二叉堆)，然后我們根據這顆新完全二叉樹再次構造出最大堆即可。
刪除過程
3. 二叉堆的存儲結構
二叉堆的存儲結構是順序存儲，因為二叉堆是一顆完全二叉樹，在文章【二叉樹的存儲】中我們說過：完全二叉樹適合使用順序存儲結構來實現。
下圖是一個最大堆，紅色方框是對結點的編號，和數組下標一一對應。
二叉堆的順序存儲
鏈式存儲結構能夠清晰而形象地為我們展現出二叉堆中雙親結點和左右孩子的關系。但是數組中沒有指針，只有數組下標，怎么表示雙親和孩子的關系呢?
其實對于完全二叉樹來說，數組下標足矣!
現假設二叉堆中雙親結點的數組下標為 parent_index，左孩子的數組下標為 left_child_index，右孩子的數組下標為 right_child_index，那么它們之間有如下關系：
(一)left_child_index = 2 × parent_index + 1
(二)right_child_index = 2 × parent_index + 2
(三)parent_index = (left_child_index - 1) ÷ 2
(四)parent_index = (right_child_index - 2) ÷ 2
(五)right_child_index = left_child_index + 1
比如：結點 3 的下標為 3 ，則其左孩子 2 的下標為 2 × 3 + 1 = 7、右孩子 1 的下標為 2 × 3 + 2 = 8;
結點 3 的下標為 3，作為左孩子，其雙親下標為 (3 - 1) ÷ 2 = 1;結點 7 的下標為 4，作為右孩子，其雙親下標為 (4 - 2) ÷ 2 = 1;
假設某結點的數組下標為 child_index，你不知道該結點是左孩子還是右孩子，要求其雙親的下標，有
(六)parent_index = (child_index - 1) ÷ 2
比如：你不知道結點 5(下標為 5)、結點 6(下標為 6)是左孩子還是右孩子，則結點 5 和結點 6 的雙親下標分別為 (5 - 1) ÷ 2 = 2 、(6 - 1) ÷ 2 = 2。(注意，編程語言中的整型運算，所以結果不是小數)
這里，我們使用結構體實現二叉堆：
- #define MAXSIZE 20 // 數組的最大存儲空間
- typedef struct {
- int array[MAXSIZE]; // 存儲數組
- int length; // 當前堆長度（結點數）
- } BinaryHeap;
在進行實際操作之前，需要初始化二叉堆，即對數組及堆長度賦值：
- /**
- * @description: 初始化二叉堆
- * @param {BinaryHeap} *heap 二叉堆
- * @param {int} *array 數組首地址，該數組是一個無序完全二叉樹
- * @param {int} arr_length 數組長度
- * @return {*} 無
- */
- void init_heap(BinaryHeap *heap, int *array, int arr_length)
- {
- // array 拷貝到 heap 中
- memcpy(heap->array, array, arr_length * sizeof(int));
- // 設置堆長度
- heap->length = arr_length;
- }
4. 二叉堆的具體實現
4.1. 調整和構造
這里以構造最小堆為例。
要構造一個最小堆，就得調整所有的非葉子結點。而調整的依據就是比較非葉子結點和其孩子的大小。
我們約定 parent 為非葉子結點， parent_index 為其下標。child 為其孩子中較小的那個，child_index為其下標。
child 開始默認標識左孩子，那么右孩子的下標即為 child_index + 1。當左孩子小于等于右孩子時，child 不需要改變;當左孩子大于右孩子時，就得更新 child_index ，使child 標識右孩子。
下面結合下圖中值為 4 的非葉子結點為例，講述代碼如何實現。
先比較 parent 的左右孩子，左孩子較小，則 child 為左孩子，不需要更新 child_index。
parent 和 child 各就各位，發現 parent 大于 child，可以交換位置。在交換之前，先保存一下 parent 的值，即 parent_value = 4：
交換位置：先把 child的值賦給 parent，從而達到 值1 上浮的效果：
然后更新 parent_index 和 child_index，二者都往下走一層次：
然后將之前保存的 value 賦給現在的 parent，從而達到 值4 下沉的效果：
一次調整完成，但對于 值4 來說，并沒有結束，因為 值4 還沒有沉到底。
比較此時 parent 的左右孩子，發現右孩子較小，則 child 為右子樹，需要更新 child_index，使 child 標識右孩子：
現在可以交換位置了，把 child 的值賦給 parent，達到 值3 的上浮：
然后，更新 parent_index 和 child_index 的值，二者向下走一個層次：
把 value 賦給 parent，達到 值4 的下沉：
此時，child_index 已超過了二叉堆的長度，即 值4 已經到底了。
調整代碼如下：
- /**
- * @description: 針對某個非葉子結點進行到底的下沉調整
- * @param {BinaryHeap} *heap 二叉堆（無序）
- * @param {int} parent_index 某個非葉子結點
- * @return {*} 無
- */
- void adjust_for_min_heap(BinaryHeap *heap, int parent_index)
- {
- // value 保存非葉子結點的值
- int value = heap->array[parent_index];
- // child_index 標識左孩子
- int child_index = parent_index * 2 + 1;
- // 最后一個結點的下標
- int last_child_index = heap->length - 1;
- // 雙親結點 parent 至少有一個孩子
- while (child_index <= last_child_index) {
- // 如果雙親結點 parent 有左孩子和右孩子
- if (child_index < last_child_index) {
- // 比較左孩子和右孩子誰小，如果右孩子小，
- if (heap->array[child_index] > heap->array[child_index + 1]) {
- // 則 child_index 標識右孩子
- child_index = child_index + 1;
- }
- }
- // 如果雙親的值大于 child 的值
- if (value > heap->array[child_index]) {
- heap->array[parent_index] = heap->array[child_index]; // 小節點上浮
- parent_index = child_index; // 更新雙親下標
- child_index = parent_index * 2 + 1; // 更新孩子下標
- } else { // 不做操作，跳出循環
- break;
- }
- // 大節點下沉
- heap->array[parent_index] = value;
- }
- }
構造代碼如下：
- /**
- * @description: 構造最小堆
- * @param {BinaryHeap} *heap 二叉堆（無序）
- * @return {*} 無
- */
- void create_min_heap(BinaryHeap *heap)
- {
- // 每個非葉子結點都調整
- for (int i = (heap->length - 2) / 2; i >= 0; i--) {
- adjust_for_min_heap(heap, i);
- }
- }
4.2. 插入結點
只需將新結點插入二叉堆最后一個結點的下一個位置，然后重新構造二叉堆。
以最小堆為例，代碼如下：
- /**
- * @description: 向最小堆中插入一個元素
- * @param {BinaryHeap} *heap 最小堆指針
- * @param {int} elem 新元素
- * @return {*} 無
- */
- void insert_into_min_heap(BinaryHeap *heap, int elem)
- {
- if (heap->length == MAXSIZE) {
- printf("二叉堆已滿，無法插入。\n");
- return;
- }
- heap->array[heap->length] = elem; // 插入
- heap->length++; // 更新長度
- create_min_heap(heap); // 重新構造
- }
4.3. 刪除結點
將最后一個結點移動(賦值)到堆頂，然后重新構造二叉堆。
以最小堆為例，代碼如下：
- /**
- * @description: 刪除最小堆的堆頂
- * @param {BinaryHeap} *heap 最小堆指針
- * @param {int} *elem 保存變量指針
- * @return {*} 無
- */
- void delete_from_min_heap(BinaryHeap *heap, int *elem)
- {
- if (heap->length == 0) {
- printf("二叉堆空，無元素可刪。\n");
- return;
- }
- *elem = heap->array[0];
- heap->array[0] = heap->array[heap->length - 1]; // 移動到堆頂
- heap->length--; // 更新長度
- create_min_heap(heap); //重新構造
- }
5. 總結
構造最大堆的本質是：將每顆子樹的“大”結點上浮作為雙親，“小”結點下沉作為孩子。
構造最小堆的本質是：將每顆子樹的“小”結點上浮作為雙親，“大”結點下沉作為孩子。
插入結點的本質是：插入新結點至二叉堆末尾，破壞了原二叉堆的結構，然后調整新得到的完全二叉樹，重新構造二叉堆。
刪除結點的本質是：刪除堆頂，破壞了原完全二叉樹的結構，然后使用最后一個結點，重新構造完全二叉樹，再調整新得到的完全二叉樹，重新構造二叉堆。
用四個字概括就是——破而后立。
至于代碼實現，關鍵在于結點的調整，把這個搞明白，剩下的就簡單了。
以上就是二叉堆的原理和相關操作。
完整代碼請移步至 GitHub[1] | Gitee[2] 獲取。
參考資料
[1]GitHub: https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo
[2]Gitee: https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo
