web開發(fā)中二叉堆需要注意的有哪些事，相信很多沒有經(jīng)驗的人對此束手無策，為此本文總結(jié)了問題出現(xiàn)的原因和解決方法，通過這篇文章希望你能解決這個問題。
專注于為中小企業(yè)提供網(wǎng)站制作、成都網(wǎng)站制作服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)銅仁免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了成百上千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。
“二叉”自不必多說，本章主要介紹的樹都是二叉樹。那么啥是“堆”呢?
我們在日常生活中，通常會說“一堆東西”或者“堆東西”，這里的“堆”，通常指重疊放置的許多東西。
一堆東西
我們在堆東西的時候，肯定都有一個經(jīng)驗，即：為了使這堆東西更穩(wěn)定，會將比較重的、大的東西放在下面，比較輕的、小的東西放在上面。
這個經(jīng)驗放在數(shù)據(jù)結(jié)構(gòu)——二叉樹中，同樣適用。只不過“重”“大”是根據(jù)結(jié)點值的大小來判斷的，并且是在雙親結(jié)點和孩子結(jié)點之間進行比較的。
比如，結(jié)點值大的，作為孩子結(jié)點;結(jié)點值小的，作為雙親結(jié)點。
下面舉一個例子，先看下面一顆普通二叉樹，也是一顆完全二叉樹：
再看下面一顆二叉堆：
最小堆
這個二叉堆的特點是：
它是一顆完全二叉樹。事實上，該二叉堆就是由上圖的完全二叉樹經(jīng)過調(diào)整轉(zhuǎn)化而來;
任何一個雙親結(jié)點的值，均小于或等于左孩子和右孩子的值;
每條分支從根結(jié)點開始都是升序排序(如分支 1-2-3-4)。
這樣的二叉堆被稱為最小堆，它的堆頂，即根結(jié)點 A，是整棵樹的最小值。
與最小堆相對應(yīng)的是最大堆：
最大堆是一顆完全二叉樹;
它的任何一個雙親結(jié)點的值，均大于或等于左孩子和右孩子的值;
每條分支從根結(jié)點開始都是降序排序。
最大堆的堆頂，是整棵樹的最大值。
我們將上圖中的普通二叉樹轉(zhuǎn)化為最大堆，如下圖：
最大堆
給你一顆完全二叉樹，如何調(diào)整結(jié)點，構(gòu)造出一個二叉堆?下面是一顆無序的完全二叉樹：
現(xiàn)在我們想要構(gòu)造出一個最小堆，首先找到這顆完全二叉樹中所有的非葉子結(jié)點(綠色標記)：
我們要做的事是：對每個非葉子結(jié)點，做最小堆的“下沉”調(diào)整。
何謂最小堆的“下沉”調(diào)整?
對某個非葉子結(jié)點，如果該結(jié)點大于其孩子結(jié)點中最小的那個，則交換二者位置，否則不用交換。在圖上則表現(xiàn)出非葉子結(jié)點(即大值結(jié)點)“下沉”一個層次。運動是相對的，大值結(jié)點“下沉”，就相當于小值結(jié)點“上浮”。
需要注意的是，有時下沉一次是不夠的，我們需要下沉多次，確保該結(jié)點下沉到底(即它不再大于其孩子)。
所有非葉子結(jié)點，從最后一個開始，按照從右到左，從下到上的順序進行多次最小堆的下沉調(diào)整，即可構(gòu)造成最小堆。
比如對于值為 4 的非葉子結(jié)點而言，它下沉到第 3 層次后，仍然大于其孩子，這不算“下沉到底”，還需要繼續(xù)下沉到第 4 層次。至此，在分支 2-4-3-1 上，“大值”結(jié)點 4 算是下沉到底了。
下面進行分步解釋：
1.對非葉子結(jié)點 7，它小于其孩子結(jié)點 10， 不用“下沉”;
2.對非葉子結(jié)點 3，它大于其孩子結(jié)點中較大的結(jié)點 1，結(jié)點 3 要“下沉”，和結(jié)點 1 交換。顯然，結(jié)點 3 沉到底了。
3.對非葉子結(jié)點 6，它大于其孩子結(jié)點中較小的結(jié)點 5，結(jié)點 6 要“下沉”， 和結(jié)點 5 交換位置。顯然，結(jié)點 6 沉到底了。
4.對非葉子結(jié)點 4，它大于其孩子結(jié)點中最小的結(jié)點 1，結(jié)點 4 要 “下沉”，和結(jié)點 1 交換位置。顯然，結(jié)點 4 并未沉到底。
5.仍對結(jié)點 4，它大于其孩子結(jié)點中最小的結(jié)點 3，結(jié)點 4 要“下沉”， 和結(jié)點 3 交換位置。此時，結(jié)點 4 算是沉底了。
6.對非葉子結(jié)點 2，它大于其孩子結(jié)點中最小的結(jié)點 1，結(jié)點 2 要“下沉”，和結(jié)點 1 交換位置。顯然，結(jié)點 2 算是沉到底了。
至此，我們將一顆無序的完全二叉樹調(diào)整改造成了最小二叉堆，你可以檢查一下，最小堆中的所有結(jié)點皆滿足雙親的值小于孩子的值。并且，5 條分支上都是有序的。
構(gòu)造最大堆的步驟類似，不過最大堆的下沉調(diào)整是：如果某結(jié)點小于其孩子結(jié)點中最大的那個，則交換二者位置，在圖上表現(xiàn)為非葉子結(jié)點(即小值結(jié)點)“下沉”一個層次。通過多次下沉調(diào)整，使該結(jié)點不再小于其孩子。
下圖把一個無序完全二叉樹調(diào)成為最大堆：
二叉堆是一個完全二叉樹，要向其中插入結(jié)點，插入到完全二叉樹的最后一個結(jié)點的下一個位置即可。
比如向下面的一個最大堆中插入結(jié)點 11，要插到最后一個結(jié)點 4 的下一個位置。當最大堆新插入一個結(jié)點 11 時，它就不再是最大堆了，因為結(jié)點 11 破壞了原堆的結(jié)構(gòu)。所以，我們應(yīng)當將其看作一個新的完全二叉樹，然后調(diào)整新完全二叉樹再次構(gòu)造出最大堆。(調(diào)整過程見上)
插入過程
刪除操作與插入操作相反，是刪除第一個位置的元素，即刪除堆頂。
我們以刪除上圖最大堆的堆頂 11 為例。
當刪除堆頂 11 后，二叉堆原結(jié)構(gòu)被破壞，甚至不是一顆二叉樹了(變成兩顆)：
為了保持完全二叉樹的形態(tài)，我們把最后一個結(jié)點 7 補到根結(jié)點去，頂替被刪除的根結(jié)點 11。如此一來，我們又得到了一個新完全二叉樹(不是二叉堆)，然后我們根據(jù)這顆新完全二叉樹再次構(gòu)造出最大堆即可。
刪除過程
二叉堆的存儲結(jié)構(gòu)是順序存儲，因為二叉堆是一顆完全二叉樹，在文章【二叉樹的存儲】中我們說過：完全二叉樹適合使用順序存儲結(jié)構(gòu)來實現(xiàn)。
下圖是一個最大堆，紅色方框是對結(jié)點的編號，和數(shù)組下標一一對應(yīng)。
二叉堆的順序存儲
鏈式存儲結(jié)構(gòu)能夠清晰而形象地為我們展現(xiàn)出二叉堆中雙親結(jié)點和左右孩子的關(guān)系。但是數(shù)組中沒有指針，只有數(shù)組下標，怎么表示雙親和孩子的關(guān)系呢?
其實對于完全二叉樹來說，數(shù)組下標足矣!
現(xiàn)假設(shè)二叉堆中雙親結(jié)點的數(shù)組下標為 parent_index，左孩子的數(shù)組下標為 left_child_index，右孩子的數(shù)組下標為 right_child_index，那么它們之間有如下關(guān)系：
(一)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
比如：結(jié)點 3 的下標為 3 ，則其左孩子 2 的下標為 2 × 3 + 1 = 7、右孩子 1 的下標為 2 × 3 + 2 = 8;
結(jié)點 3 的下標為 3，作為左孩子，其雙親下標為 (3 - 1) ÷ 2 = 1;結(jié)點 7 的下標為 4，作為右孩子，其雙親下標為 (4 - 2) ÷ 2 = 1;
假設(shè)某結(jié)點的數(shù)組下標為 child_index，你不知道該結(jié)點是左孩子還是右孩子，要求其雙親的下標，有
(六)parent_index = (child_index - 1) ÷ 2
比如：你不知道結(jié)點 5(下標為 5)、結(jié)點 6(下標為 6)是左孩子還是右孩子，則結(jié)點 5 和結(jié)點 6 的雙親下標分別為 (5 - 1) ÷ 2 = 2 、(6 - 1) ÷ 2 = 2。(注意，編程語言中的整型運算，所以結(jié)果不是小數(shù))
這里，我們使用結(jié)構(gòu)體實現(xiàn)二叉堆：
重慶分公司
重慶分公司
#define MAXSIZE 20 // 數(shù)組的最大存儲空間 typedef struct { int array[MAXSIZE]; // 存儲數(shù)組 int length; // 當前堆長度（結(jié)點數(shù)） } BinaryHeap;在進行實際操作之前，需要初始化二叉堆，即對數(shù)組及堆長度賦值：
/** * @description: 初始化二叉堆 * @param {BinaryHeap} *heap 二叉堆 * @param {int} *array 數(shù)組首地址，該數(shù)組是一個無序完全二叉樹 * @param {int} arr_length 數(shù)組長度 * @return {*} 無 */ void init_heap(BinaryHeap *heap, int *array, int arr_length) { // array 拷貝到 heap 中 memcpy(heap->array, array, arr_length * sizeof(int)); // 設(shè)置堆長度 heap->length = arr_length; }這里以構(gòu)造最小堆為例。
要構(gòu)造一個最小堆，就得調(diào)整所有的非葉子結(jié)點。而調(diào)整的依據(jù)就是比較非葉子結(jié)點和其孩子的大小。
我們約定 parent 為非葉子結(jié)點， parent_index 為其下標。child 為其孩子中較小的那個，child_index為其下標。
child 開始默認標識左孩子，那么右孩子的下標即為 child_index + 1。當左孩子小于等于右孩子時，child 不需要改變;當左孩子大于右孩子時，就得更新 child_index ，使child 標識右孩子。
下面結(jié)合下圖中值為 4 的非葉子結(jié)點為例，講述代碼如何實現(xiàn)。
先比較 parent 的左右孩子，左孩子較小，則 child 為左孩子，不需要更新 child_index。
parent 和 child 各就各位，發(fā)現(xiàn) parent 大于 child，可以交換位置。在交換之前，先保存一下 parent 的值，即 parent_value = 4：
交換位置：先把 child的值賦給 parent，從而達到 值1 上浮的效果：
然后更新 parent_index 和 child_index，二者都往下走一層次：
然后將之前保存的 value 賦給現(xiàn)在的 parent，從而達到 值4 下沉的效果：
一次調(diào)整完成，但對于 值4 來說，并沒有結(jié)束，因為 值4 還沒有沉到底。
比較此時 parent 的左右孩子，發(fā)現(xiàn)右孩子較小，則 child 為右子樹，需要更新 child_index，使 child 標識右孩子：
現(xiàn)在可以交換位置了，把 child 的值賦給 parent，達到 值3 的上?。?/p>
然后，更新 parent_index 和 child_index 的值，二者向下走一個層次：
把 value 賦給 parent，達到 值4 的下沉：
此時，child_index 已超過了二叉堆的長度，即 值4 已經(jīng)到底了。
調(diào)整代碼如下：
/** * @description: 針對某個非葉子結(jié)點進行到底的下沉調(diào)整 * @param {BinaryHeap} *heap 二叉堆（無序） * @param {int} parent_index 某個非葉子結(jié)點 * @return {*} 無 */ void adjust_for_min_heap(BinaryHeap *heap, int parent_index) { // value 保存非葉子結(jié)點的值 int value = heap->array[parent_index]; // child_index 標識左孩子 int child_index = parent_index * 2 + 1; // 最后一個結(jié)點的下標 int last_child_index = heap->length - 1; // 雙親結(jié)點 parent 至少有一個孩子 while (child_index <= last_child_index) { // 如果雙親結(jié)點 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]; // 小節(jié)點上浮 parent_index = child_index; // 更新雙親下標 child_index = parent_index * 2 + 1; // 更新孩子下標 } else { // 不做操作，跳出循環(huán) break; } // 大節(jié)點下沉 heap->array[parent_index] = value; } }構(gòu)造代碼如下：
/** * @description: 構(gòu)造最小堆 * @param {BinaryHeap} *heap 二叉堆（無序） * @return {*} 無 */ void create_min_heap(BinaryHeap *heap) { // 每個非葉子結(jié)點都調(diào)整 for (int i = (heap->length - 2) / 2; i >= 0; i--) { adjust_for_min_heap(heap, i); } }只需將新結(jié)點插入二叉堆最后一個結(jié)點的下一個位置，然后重新構(gòu)造二叉堆。
以最小堆為例，代碼如下：
/** * @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); // 重新構(gòu)造 }將最后一個結(jié)點移動(賦值)到堆頂，然后重新構(gòu)造二叉堆。
以最小堆為例，代碼如下：
/** * @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); //重新構(gòu)造 }構(gòu)造最大堆的本質(zhì)是：將每顆子樹的“大”結(jié)點上浮作為雙親，“小”結(jié)點下沉作為孩子。
構(gòu)造最小堆的本質(zhì)是：將每顆子樹的“小”結(jié)點上浮作為雙親，“大”結(jié)點下沉作為孩子。
插入結(jié)點的本質(zhì)是：插入新結(jié)點至二叉堆末尾，破壞了原二叉堆的結(jié)構(gòu)，然后調(diào)整新得到的完全二叉樹，重新構(gòu)造二叉堆。
刪除結(jié)點的本質(zhì)是：刪除堆頂，破壞了原完全二叉樹的結(jié)構(gòu)，然后使用最后一個結(jié)點，重新構(gòu)造完全二叉樹，再調(diào)整新得到的完全二叉樹，重新構(gòu)造二叉堆。
用四個字概括就是——破而后立。
至于代碼實現(xiàn)，關(guān)鍵在于結(jié)點的調(diào)整，把這個搞明白，剩下的就簡單了。
以上就是二叉堆的原理和相關(guān)操作。
看完上述內(nèi)容，你們掌握web開發(fā)中二叉堆需要注意的有哪些事的方法了嗎？如果還想學(xué)到更多技能或想了解更多相關(guān)內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！
