日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢
選擇下列產(chǎn)品馬上在線溝通
服務(wù)時間：8:30-17:00
你可能遇到了下面的問題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
搞懂二叉堆的那些事

1. 什么是二叉堆?

“二叉”自不必多說，本章主要介紹的樹都是二叉樹。那么啥是“堆”呢?

站在用戶的角度思考問題，與客戶深入溝通，找到溫江網(wǎng)站設(shè)計與溫江網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個性化、用戶體驗(yàn)好的作品，建站類型包括：網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名申請、網(wǎng)絡(luò)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋溫江地區(qū)。

我們在日常生活中，通常會說“一堆東西”或者“堆東西”，這里的“堆”，通常指重疊放置的許多東西。

 [[397348]]

一堆東西

我們在堆東西的時候，肯定都有一個經(jīng)驗(yàn)，即：為了使這堆東西更穩(wěn)定，會將比較重的、大的東西放在下面，比較輕的、小的東西放在上面。

這個經(jīng)驗(yàn)放在數(shù)據(jù)結(jié)構(gòu)——二叉樹中，同樣適用。只不過“重”“大”是根據(jù)結(jié)點(diǎn)值的大小來判斷的，并且是在雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間進(jìn)行比較的。

比如，結(jié)點(diǎn)值大的，作為孩子結(jié)點(diǎn);結(jié)點(diǎn)值小的，作為雙親結(jié)點(diǎn)。

下面舉一個例子，先看下面一顆普通二叉樹，也是一顆完全二叉樹：

再看下面一顆二叉堆：

最小堆

這個二叉堆的特點(diǎn)是：

  • 它是一顆完全二叉樹。事實(shí)上，該二叉堆就是由上圖的完全二叉樹經(jīng)過調(diào)整轉(zhuǎn)化而來;
  • 任何一個雙親結(jié)點(diǎn)的值，均小于或等于左孩子和右孩子的值;
  • 每條分支從根結(jié)點(diǎn)開始都是升序排序(如分支 1-2-3-4)。

這樣的二叉堆被稱為最小堆，它的堆頂，即根結(jié)點(diǎn) A，是整棵樹的最小值。

與最小堆相對應(yīng)的是最大堆：

  • 最大堆是一顆完全二叉樹;
  • 它的任何一個雙親結(jié)點(diǎn)的值，均大于或等于左孩子和右孩子的值;
  • 每條分支從根結(jié)點(diǎn)開始都是降序排序。

最大堆的堆頂，是整棵樹的最大值。

我們將上圖中的普通二叉樹轉(zhuǎn)化為最大堆，如下圖：

最大堆

2. 二叉堆的操作

2.1. 構(gòu)造二叉堆

給你一顆完全二叉樹，如何調(diào)整結(jié)點(diǎn)，構(gòu)造出一個二叉堆?下面是一顆無序的完全二叉樹：

現(xiàn)在我們想要構(gòu)造出一個最小堆，首先找到這顆完全二叉樹中所有的非葉子結(jié)點(diǎn)(綠色標(biāo)記)：

我們要做的事是：對每個非葉子結(jié)點(diǎn)，做最小堆的“下沉”調(diào)整。

何謂最小堆的“下沉”調(diào)整?

對某個非葉子結(jié)點(diǎn)，如果該結(jié)點(diǎn)大于其孩子結(jié)點(diǎn)中最小的那個，則交換二者位置，否則不用交換。在圖上則表現(xiàn)出非葉子結(jié)點(diǎn)(即大值結(jié)點(diǎn))“下沉”一個層次。運(yùn)動是相對的，大值結(jié)點(diǎn)“下沉”，就相當(dāng)于小值結(jié)點(diǎn)“上浮”。

需要注意的是，有時下沉一次是不夠的，我們需要下沉多次，確保該結(jié)點(diǎn)下沉到底(即它不再大于其孩子)。

所有非葉子結(jié)點(diǎn)，從最后一個開始，按照從右到左，從下到上的順序進(jìn)行多次最小堆的下沉調(diào)整，即可構(gòu)造成最小堆。

比如對于值為 4 的非葉子結(jié)點(diǎn)而言，它下沉到第 3 層次后，仍然大于其孩子，這不算“下沉到底”，還需要繼續(xù)下沉到第 4 層次。至此，在分支 2-4-3-1 上，“大值”結(jié)點(diǎn) 4 算是下沉到底了。

下面進(jìn)行分步解釋：

1.對非葉子結(jié)點(diǎn) 7，它小于其孩子結(jié)點(diǎn) 10， 不用“下沉”;

2.對非葉子結(jié)點(diǎn) 3，它大于其孩子結(jié)點(diǎn)中較大的結(jié)點(diǎn) 1，結(jié)點(diǎn) 3 要“下沉”，和結(jié)點(diǎn) 1 交換。顯然，結(jié)點(diǎn) 3 沉到底了。

 

3.對非葉子結(jié)點(diǎn) 6，它大于其孩子結(jié)點(diǎn)中較小的結(jié)點(diǎn) 5，結(jié)點(diǎn) 6 要“下沉”， 和結(jié)點(diǎn) 5 交換位置。顯然，結(jié)點(diǎn) 6 沉到底了。

4.對非葉子結(jié)點(diǎn) 4，它大于其孩子結(jié)點(diǎn)中最小的結(jié)點(diǎn) 1，結(jié)點(diǎn) 4 要 “下沉”，和結(jié)點(diǎn) 1 交換位置。顯然，結(jié)點(diǎn) 4 并未沉到底。

5.仍對結(jié)點(diǎn) 4，它大于其孩子結(jié)點(diǎn)中最小的結(jié)點(diǎn) 3，結(jié)點(diǎn) 4 要“下沉”， 和結(jié)點(diǎn) 3 交換位置。此時，結(jié)點(diǎn) 4 算是沉底了。

6.對非葉子結(jié)點(diǎn) 2，它大于其孩子結(jié)點(diǎn)中最小的結(jié)點(diǎn) 1，結(jié)點(diǎn) 2 要“下沉”，和結(jié)點(diǎn) 1 交換位置。顯然，結(jié)點(diǎn) 2 算是沉到底了。

至此，我們將一顆無序的完全二叉樹調(diào)整改造成了最小二叉堆，你可以檢查一下，最小堆中的所有結(jié)點(diǎn)皆滿足雙親的值小于孩子的值。并且，5 條分支上都是有序的。

構(gòu)造最大堆的步驟類似，不過最大堆的下沉調(diào)整是：如果某結(jié)點(diǎn)小于其孩子結(jié)點(diǎn)中最大的那個，則交換二者位置，在圖上表現(xiàn)為非葉子結(jié)點(diǎn)(即小值結(jié)點(diǎn))“下沉”一個層次。通過多次下沉調(diào)整，使該結(jié)點(diǎn)不再小于其孩子。

下圖把一個無序完全二叉樹調(diào)成為最大堆：

2.2. 插入結(jié)點(diǎn)

二叉堆是一個完全二叉樹，要向其中插入結(jié)點(diǎn)，插入到完全二叉樹的最后一個結(jié)點(diǎn)的下一個位置即可。

比如向下面的一個最大堆中插入結(jié)點(diǎn) 11，要插到最后一個結(jié)點(diǎn) 4 的下一個位置。當(dāng)最大堆新插入一個結(jié)點(diǎn) 11 時，它就不再是最大堆了，因?yàn)榻Y(jié)點(diǎn) 11 破壞了原堆的結(jié)構(gòu)。所以，我們應(yīng)當(dāng)將其看作一個新的完全二叉樹，然后調(diào)整新完全二叉樹再次構(gòu)造出最大堆。(調(diào)整過程見上)

插入過程

2.3. 刪除結(jié)點(diǎn)

刪除操作與插入操作相反，是刪除第一個位置的元素，即刪除堆頂。

我們以刪除上圖最大堆的堆頂 11 為例。

當(dāng)刪除堆頂 11 后，二叉堆原結(jié)構(gòu)被破壞，甚至不是一顆二叉樹了(變成兩顆)：

為了保持完全二叉樹的形態(tài)，我們把最后一個結(jié)點(diǎn) 7 補(bǔ)到根結(jié)點(diǎn)去，頂替被刪除的根結(jié)點(diǎn) 11。如此一來，我們又得到了一個新完全二叉樹(不是二叉堆)，然后我們根據(jù)這顆新完全二叉樹再次構(gòu)造出最大堆即可。

刪除過程

3. 二叉堆的存儲結(jié)構(gòu)

二叉堆的存儲結(jié)構(gòu)是順序存儲，因?yàn)槎娑咽且活w完全二叉樹，在文章【二叉樹的存儲】中我們說過：完全二叉樹適合使用順序存儲結(jié)構(gòu)來實(shí)現(xiàn)。

下圖是一個最大堆，紅色方框是對結(jié)點(diǎn)的編號，和數(shù)組下標(biāo)一一對應(yīng)。

 

二叉堆的順序存儲

鏈?zhǔn)酱鎯Y(jié)構(gòu)能夠清晰而形象地為我們展現(xiàn)出二叉堆中雙親結(jié)點(diǎn)和左右孩子的關(guān)系。但是數(shù)組中沒有指針，只有數(shù)組下標(biāo)，怎么表示雙親和孩子的關(guān)系呢?

其實(shí)對于完全二叉樹來說，數(shù)組下標(biāo)足矣!

現(xiàn)假設(shè)二叉堆中雙親結(jié)點(diǎn)的數(shù)組下標(biāo)為 parent_index，左孩子的數(shù)組下標(biāo)為 left_child_index，右孩子的數(shù)組下標(biāo)為 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é)點(diǎn) 3 的下標(biāo)為 3 ，則其左孩子 2 的下標(biāo)為 2 × 3 + 1 = 7、右孩子 1 的下標(biāo)為 2 × 3 + 2 = 8;

結(jié)點(diǎn) 3 的下標(biāo)為 3，作為左孩子，其雙親下標(biāo)為 (3 - 1) ÷ 2 = 1;結(jié)點(diǎn) 7 的下標(biāo)為 4，作為右孩子，其雙親下標(biāo)為 (4 - 2) ÷ 2 = 1;

假設(shè)某結(jié)點(diǎn)的數(shù)組下標(biāo)為 child_index，你不知道該結(jié)點(diǎn)是左孩子還是右孩子，要求其雙親的下標(biāo)，有

(六)parent_index = (child_index - 1) ÷ 2

比如：你不知道結(jié)點(diǎn) 5(下標(biāo)為 5)、結(jié)點(diǎn) 6(下標(biāo)為 6)是左孩子還是右孩子，則結(jié)點(diǎn) 5 和結(jié)點(diǎn) 6 的雙親下標(biāo)分別為 (5 - 1) ÷ 2 = 2 、(6 - 1) ÷ 2 = 2。(注意，編程語言中的整型運(yùn)算，所以結(jié)果不是小數(shù))

這里，我們使用結(jié)構(gòu)體實(shí)現(xiàn)二叉堆：

 
 
 
 
    
  
  
  
  
  1. #define MAXSIZE 20 // 數(shù)組的最大存儲空間 
    2.   
  
  
  
  2.  
    3.   
  
  
  
  3. typedef struct { 
    4.   
  
  
  
  4.     int array[MAXSIZE]; // 存儲數(shù)組 
    5.   
  
  
  
  5.     int length; // 當(dāng)前堆長度（結(jié)點(diǎn)數(shù)） 
    6.   
  
  
  
  6. } BinaryHeap; 
    7.

在進(jìn)行實(shí)際操作之前，需要初始化二叉堆，即對數(shù)組及堆長度賦值：

 
 
 
 
    
  
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * @description: 初始化二叉堆 
    3.   
  
  
  
  3.  * @param {BinaryHeap} *heap 二叉堆 
    4.   
  
  
  
  4.  * @param {int} *array 數(shù)組首地址，該數(shù)組是一個無序完全二叉樹 
    5.   
  
  
  
  5.  * @param {int} arr_length 數(shù)組長度 
    6.   
  
  
  
  6.  * @return {*} 無 
    7.   
  
  
  
  7.  */ 
    8.   
  
  
  
  8. void init_heap(BinaryHeap *heap, int *array, int arr_length) 
    9.   
  
  
  
  9. { 
    10.   
  
  
  
  10.     // array 拷貝到 heap 中 
    11.   
  
  
  
  11.     memcpy(heap->array, array, arr_length * sizeof(int)); 
    12.   
  
  
  
  12.     // 設(shè)置堆長度 
    13.   
  
  
  
  13.     heap->length = arr_length; 
    14.   
  
  
  
  14. } 
    15.

4. 二叉堆的具體實(shí)現(xiàn)

4.1. 調(diào)整和構(gòu)造

這里以構(gòu)造最小堆為例。

要構(gòu)造一個最小堆，就得調(diào)整所有的非葉子結(jié)點(diǎn)。而調(diào)整的依據(jù)就是比較非葉子結(jié)點(diǎn)和其孩子的大小。

我們約定 parent 為非葉子結(jié)點(diǎn)， parent_index 為其下標(biāo)。child 為其孩子中較小的那個，child_index為其下標(biāo)。

child 開始默認(rèn)標(biāo)識左孩子，那么右孩子的下標(biāo)即為 child_index + 1。當(dāng)左孩子小于等于右孩子時，child 不需要改變;當(dāng)左孩子大于右孩子時，就得更新 child_index ，使child 標(biāo)識右孩子。

下面結(jié)合下圖中值為 4 的非葉子結(jié)點(diǎn)為例，講述代碼如何實(shí)現(xiàn)。

先比較 parent 的左右孩子，左孩子較小，則 child 為左孩子，不需要更新 child_index。

parent 和 child 各就各位，發(fā)現(xiàn) parent 大于 child，可以交換位置。在交換之前，先保存一下 parent 的值，即 parent_value = 4：

交換位置：先把 child的值賦給 parent，從而達(dá)到 值1 上浮的效果：

 

然后更新 parent_index 和 child_index，二者都往下走一層次：

然后將之前保存的 value 賦給現(xiàn)在的 parent，從而達(dá)到 值4 下沉的效果：

一次調(diào)整完成，但對于 值4 來說，并沒有結(jié)束，因?yàn)?值4 還沒有沉到底。

比較此時 parent 的左右孩子，發(fā)現(xiàn)右孩子較小，則 child 為右子樹，需要更新 child_index，使 child 標(biāo)識右孩子：

現(xiàn)在可以交換位置了，把 child 的值賦給 parent，達(dá)到 值3 的上?。?/p>

 

然后，更新 parent_index 和 child_index 的值，二者向下走一個層次：

把 value 賦給 parent，達(dá)到 值4 的下沉：

 

此時，child_index 已超過了二叉堆的長度，即 值4 已經(jīng)到底了。

調(diào)整代碼如下：

 
 
 
 
    
  
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * @description: 針對某個非葉子結(jié)點(diǎn)進(jìn)行到底的下沉調(diào)整 
    3.   
  
  
  
  3.  * @param {BinaryHeap} *heap 二叉堆（無序） 
    4.   
  
  
  
  4.  * @param {int} parent_index 某個非葉子結(jié)點(diǎn) 
    5.   
  
  
  
  5.  * @return {*} 無 
    6.   
  
  
  
  6.  */ 
    7.   
  
  
  
  7. void adjust_for_min_heap(BinaryHeap *heap, int parent_index) 
    8.   
  
  
  
  8. { 
    9.   
  
  
  
  9.     // value 保存非葉子結(jié)點(diǎn)的值 
    10.   
  
  
  
  10.     int value = heap->array[parent_index]; 
    11.   
  
  
  
  11.     // child_index 標(biāo)識左孩子 
    12.   
  
  
  
  12.     int child_index = parent_index * 2 + 1; 
    13.   
  
  
  
  13.     // 最后一個結(jié)點(diǎn)的下標(biāo) 
    14.   
  
  
  
  14.     int last_child_index = heap->length - 1; 
    15.   
  
  
  
  15.  
    16.   
  
  
  
  16.     // 雙親結(jié)點(diǎn) parent 至少有一個孩子 
    17.   
  
  
  
  17.     while (child_index <= last_child_index) { 
    18.   
  
  
  
  18.         // 如果雙親結(jié)點(diǎn) parent 有左孩子和右孩子 
    19.   
  
  
  
  19.         if (child_index < last_child_index) { 
    20.   
  
  
  
  20.             // 比較左孩子和右孩子誰小，如果右孩子小， 
    21.   
  
  
  
  21.             if (heap->array[child_index] > heap->array[child_index + 1]) { 
    22.   
  
  
  
  22.                 // 則 child_index 標(biāo)識右孩子 
    23.   
  
  
  
  23.                 child_index = child_index + 1; 
    24.   
  
  
  
  24.             } 
    25.   
  
  
  
  25.         } 
    26.   
  
  
  
  26.         // 如果雙親的值大于 child 的值 
    27.   
  
  
  
  27.         if (value > heap->array[child_index]) { 
    28.   
  
  
  
  28.             heap->array[parent_index] = heap->array[child_index]; // 小節(jié)點(diǎn)上浮 
    29.   
  
  
  
  29.             parent_index = child_index; // 更新雙親下標(biāo) 
    30.   
  
  
  
  30.             child_index = parent_index * 2 + 1; // 更新孩子下標(biāo) 
    31.   
  
  
  
  31.         } else { // 不做操作，跳出循環(huán) 
    32.   
  
  
  
  32.             break; 
    33.   
  
  
  
  33.         } 
    34.   
  
  
  
  34.         // 大節(jié)點(diǎn)下沉 
    35.   
  
  
  
  35.         heap->array[parent_index] = value; 
    36.   
  
  
  
  36.     } 
    37.   
  
  
  
  37. } 
    38.

構(gòu)造代碼如下：

 
 
 
 
    
  
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * @description: 構(gòu)造最小堆 
    3.   
  
  
  
  3.  * @param {BinaryHeap} *heap 二叉堆（無序） 
    4.   
  
  
  
  4.  * @return {*} 無 
    5.   
  
  
  
  5.  */ 
    6.   
  
  
  
  6. void create_min_heap(BinaryHeap *heap) 
    7.   
  
  
  
  7. { 
    8.   
  
  
  
  8.     // 每個非葉子結(jié)點(diǎn)都調(diào)整 
    9.   
  
  
  
  9.     for (int i = (heap->length - 2) / 2; i >= 0; i--) { 
    10.   
  
  
  
  10.         adjust_for_min_heap(heap, i); 
    11.   
  
  
  
  11.     } 
    12.   
  
  
  
  12. } 
    13.

4.2. 插入結(jié)點(diǎn)

只需將新結(jié)點(diǎn)插入二叉堆最后一個結(jié)點(diǎn)的下一個位置，然后重新構(gòu)造二叉堆。

以最小堆為例，代碼如下：

 
 
 
 
    
  
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * @description: 向最小堆中插入一個元素 
    3.   
  
  
  
  3.  * @param {BinaryHeap} *heap 最小堆指針 
    4.   
  
  
  
  4.  * @param {int} elem 新元素 
    5.   
  
  
  
  5.  * @return {*} 無 
    6.   
  
  
  
  6.  */ 
    7.   
  
  
  
  7. void insert_into_min_heap(BinaryHeap *heap, int elem) 
    8.   
  
  
  
  8. { 
    9.   
  
  
  
  9.     if (heap->length == MAXSIZE) { 
    10.   
  
  
  
  10.         printf("二叉堆已滿，無法插入。\n"); 
    11.   
  
  
  
  11.         return; 
    12.   
  
  
  
  12.     } 
    13.   
  
  
  
  13.     heap->array[heap->length] = elem; // 插入 
    14.   
  
  
  
  14.     heap->length++; // 更新長度 
    15.   
  
  
  
  15.     create_min_heap(heap); // 重新構(gòu)造 
    16.   
  
  
  
  16. } 
    17.

4.3. 刪除結(jié)點(diǎn)

將最后一個結(jié)點(diǎn)移動(賦值)到堆頂，然后重新構(gòu)造二叉堆。

以最小堆為例，代碼如下：

 
 
 
 
    
  
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * @description: 刪除最小堆的堆頂 
    3.   
  
  
  
  3.  * @param {BinaryHeap} *heap 最小堆指針 
    4.   
  
  
  
  4.  * @param {int} *elem 保存變量指針 
    5.   
  
  
  
  5.  * @return {*} 無 
    6.   
  
  
  
  6.  */ 
    7.   
  
  
  
  7. void delete_from_min_heap(BinaryHeap *heap, int *elem) 
    8.   
  
  
  
  8. { 
    9.   
  
  
  
  9.     if (heap->length == 0) { 
    10.   
  
  
  
  10.         printf("二叉堆空，無元素可刪。\n"); 
    11.   
  
  
  
  11.         return; 
    12.   
  
  
  
  12.     } 
    13.   
  
  
  
  13.     *elem = heap->array[0]; 
    14.   
  
  
  
  14.     heap->array[0] = heap->array[heap->length - 1]; // 移動到堆頂 
    15.   
  
  
  
  15.     heap->length--; // 更新長度 
    16.   
  
  
  
  16.     create_min_heap(heap); //重新構(gòu)造 
    17.   
  
  
  
  17. } 
    18.

5. 總結(jié)

構(gòu)造最大堆的本質(zhì)是：將每顆子樹的“大”結(jié)點(diǎn)上浮作為雙親，“小”結(jié)點(diǎn)下沉作為孩子。

構(gòu)造最小堆的本質(zhì)是：將每顆子樹的“小”結(jié)點(diǎn)上浮作為雙親，“大”結(jié)點(diǎn)下沉作為孩子。

插入結(jié)點(diǎn)的本質(zhì)是：插入新結(jié)點(diǎn)至二叉堆末尾，破壞了原二叉堆的結(jié)構(gòu)，然后調(diào)整新得到的完全二叉樹，重新構(gòu)造二叉堆。

刪除結(jié)點(diǎn)的本質(zhì)是：刪除堆頂，破壞了原完全二叉樹的結(jié)構(gòu)，然后使用最后一個結(jié)點(diǎn)，重新構(gòu)造完全二叉樹，再調(diào)整新得到的完全二叉樹，重新構(gòu)造二叉堆。

用四個字概括就是——破而后立。

至于代碼實(shí)現(xiàn)，關(guān)鍵在于結(jié)點(diǎn)的調(diào)整，把這個搞明白，剩下的就簡單了。

以上就是二叉堆的原理和相關(guān)操作。

完整代碼請移步至 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

 


當(dāng)前題目：搞懂二叉堆的那些事
網(wǎng)頁地址：http://www.5511xx.com/article/cdcdsod.html