圖解：什么是二叉堆？

作者：景禹 2020-08-31 07:43:58

開發(fā) 前端

在正式開始學(xué)習(xí)堆之前，一定要大腦里回顧一下什么是完全二叉樹，因?yàn)樗投芽墒窍⑾⑾嚓P(guān)奧!

[[339907]]

在正式開始學(xué)習(xí)堆之前，一定要大腦里回顧一下什么是完全二叉樹，因?yàn)樗投芽墒窍⑾⑾嚓P(guān)奧!

如果二叉樹中除了葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的度都為 2，則此二叉樹稱為滿二叉樹。

而如果二叉樹中除去最后一層節(jié)點(diǎn)為滿二叉樹，且最后一層的結(jié)點(diǎn)依次從左到右分布，則此二叉樹被稱為完全二叉樹。

所以可以滿二叉樹必然是完全二叉樹，關(guān)于完全二叉樹不清楚可以查看一文讀懂有關(guān)Tree的前世今生這篇文章。

對于任意一個(gè)完全二叉樹來說，如果將含有的結(jié)點(diǎn)按照層次從左到右依次標(biāo)號(如上圖))，對于任意一個(gè)結(jié)點(diǎn) i ，完全二叉樹(二叉堆)滿足以下幾個(gè)結(jié)論：

當(dāng)i>1時(shí)，父親結(jié)點(diǎn)為結(jié)點(diǎn) 。i/2時(shí)，i=1時(shí)，表示的是根結(jié)點(diǎn)，無父親結(jié)點(diǎn));比如結(jié)點(diǎn) 45 的的標(biāo)號為 4 ，其父結(jié)點(diǎn) 15 的標(biāo)號為 2 ，而2=4/2 ;

如果2Xi >n(總結(jié)點(diǎn)的個(gè)數(shù)) ，則結(jié)點(diǎn) 肯定沒有左孩子(為葉子結(jié)點(diǎn));否則其左孩子是結(jié)點(diǎn)2Xi 。比如結(jié)點(diǎn) 15 的標(biāo)號為 2 ，其左孩子結(jié)點(diǎn)為 4 ;

如果2X+1 >n，則結(jié)點(diǎn)i 肯定沒有右孩子;否則右孩子是結(jié)點(diǎn)2Xi+1 。

堆堆(Heap)是一類基于完全二叉樹的特殊數(shù)據(jù)結(jié)構(gòu)。通常將堆分為兩種類型：

大頂堆(Max Heap)：在大頂堆中，根結(jié)點(diǎn)的值必須大于它的孩子結(jié)點(diǎn)的值，對于二叉樹中所有子樹也應(yīng)遞歸地滿足這一特性。
小頂堆(Min Heap)：在小頂堆中，根結(jié)點(diǎn)的值必須小于它的孩子結(jié)點(diǎn)的值，且對于二叉樹的所有子樹也均遞歸地滿足同一特性。

不是所有的人都是計(jì)算機(jī)出身，上過正課的小伙伴，所以我在嘮叨一下概念。

小頂堆就是以任意一個(gè)結(jié)點(diǎn)作為根，其左右孩子都要大于等于該結(jié)點(diǎn)的值，所以整顆樹的根結(jié)點(diǎn)一定是樹中值最小的結(jié)點(diǎn)，而大頂堆正好特性相反。

二叉堆

二叉堆是滿足下面屬性的一顆二叉樹：

二叉堆必定是一顆完全二叉樹。二叉堆的此屬性也決定了他們適合存儲在數(shù)組當(dāng)中。
二叉堆要么是小頂堆，要么是大頂堆。小頂二叉堆中的根結(jié)點(diǎn)的值是整棵樹中的最小值，而且二叉樹中的所有頂點(diǎn)及其子樹均滿足這一特性。大頂堆與小頂堆類似，大頂堆的根結(jié)點(diǎn)的值是整棵樹中的最大值，而且二叉樹中所有結(jié)點(diǎn)的值也均大于等于其子樹結(jié)點(diǎn)。

由于小頂堆和大頂堆除了在頂點(diǎn)的大小關(guān)系上不一致，兩者均是一顆全完二叉樹，下面的所有講解，都以小頂堆為例進(jìn)行說明，會了小頂堆，大頂堆你自己都能寫出來。

這就是兩個(gè)典型的小頂堆。

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

二叉堆是一顆完全二叉樹，一般用數(shù)組表示。其中根元素用 arr[0] 表示，而其他結(jié)點(diǎn)(第i 個(gè)結(jié)點(diǎn)的存儲位置)滿足下表中的特性：

數(shù)組表示含義

數(shù)組表示	含義
arr[(i-1)/2]	第 i 個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)
arr[2*i + 1]	第 i 個(gè)結(jié)點(diǎn)的左孩子結(jié)點(diǎn)
arr[2*i + 2]	第 i 個(gè)結(jié)點(diǎn)的右孩子結(jié)點(diǎn)

二叉堆的這種表示方式和性質(zhì)其本質(zhì)上與一顆完全二叉樹自身所具有的特性一一對應(yīng)。

小頂二叉堆的常見操作

獲取小頂二叉堆的根元素 getMin() ，這一操作的時(shí)間復(fù)雜度為 ;按照上面的存儲結(jié)構(gòu)，根結(jié)點(diǎn)為 arr[0] ，返回即可。

int getMin() 
{ 
    return arr[0]; 
}

移除小頂二叉堆的最小元素 removeMin() ，這一操作的時(shí)間復(fù)雜度為，因?yàn)橐瞥№敹娑训淖钚≡?即堆頂元素)之后，需要對堆進(jìn)行調(diào)整，從而使得堆依舊維持其屬性，一般將調(diào)整的過程稱為堆化 (heapify)。

int removeMin()  
{  
    if (heap_size <= 0)  
        return INT_MAX;  
    if (heap_size == 1)  
    {  
        heap_size--;  
        return harr[0];  
    }  
   
    // 存儲最小值（當(dāng)前的堆頂元素），將堆中的最后一個(gè)元素放到堆頂，然后進(jìn)行Heapify() 
    int root = harr[0];  
    harr[0] = harr[heap_size-1];  
    heap_size--;  
    MinHeapify(0);  
   
    return root;  
}

我們以下圖為例進(jìn)行說明：

刪除堆頂元素 10 ，然后將最后一個(gè)元素 50 作為小頂堆的堆頂：

然后從堆頂元素 50 開始進(jìn)行堆化。

第一步：計(jì)算當(dāng)前堆頂元素 50(i = 0) 的左孩子，以及右孩子，然后比較三者，選擇出三者的最小值 15 ，將 15 和 50 進(jìn)行交換，繼續(xù)對值為 50 的頂點(diǎn)(i = 1)的子樹進(jìn)行堆化：

第二步：計(jì)算當(dāng)前要進(jìn)行堆化的結(jié)點(diǎn) 50(i = 1) 的左右孩子，左孩子，右孩子不存在，比較 50 和 45 ，發(fā)現(xiàn) 50 > 45 ，交換兩者，然后繼續(xù)對值為 50 的頂點(diǎn)(i = 3)的子樹進(jìn)行堆化：

第三步：計(jì)算要進(jìn)行堆化的結(jié)點(diǎn) 50 (i = 1) 的左右孩子，發(fā)現(xiàn)不存在，所以結(jié)點(diǎn) 50 已經(jīng)到葉子結(jié)點(diǎn)，整棵樹堆化完成啦(其實(shí)這個(gè)堆化的過程還是挺簡單的，我們后面刪除等還會用到堆化的，這里不明白，不影響下面繼續(xù)噠!)。

更新給定下標(biāo)的值 updateKey(int i，int new_val) ，這里有一個(gè)假設(shè)是 new_val < val 的值，如果 new_val > val ，那么就是對更新的結(jié)點(diǎn)進(jìn)行堆化啦，所以就不單獨(dú)進(jìn)行處理。還想兩種都處理，加個(gè) If...else... 就可以啦。

void updateKey(int i, int new_val)  
{  
    harr[i] = new_val;  
    while (i != 0 && harr[parent(i)] > harr[i])  
    {  
       swap(&harr[i], &harr[parent(i)]);  
       i = parent(i);  
    }  
}

這個(gè)操作和堆化的操作相反，我們是從被更新的結(jié)點(diǎn)開始向上回溯，直到結(jié)點(diǎn)的值大于父結(jié)點(diǎn)的值停止。

我們將下標(biāo)為 4 的結(jié)點(diǎn) 50 的值更新為 8 ：

第一步：判斷結(jié)點(diǎn) 8(i = 4) 的父結(jié)點(diǎn)的大小關(guān)系，8 < 15 ，交換 8和 15 ，然后結(jié)點(diǎn) 8(i = 1) 繼續(xù)做判斷：

第二步：判斷結(jié)點(diǎn) 8(i = 1) 與其父節(jié)點(diǎn)的大小關(guān)系，8 < 10 , 交換8 和10 ：

第三步：判斷結(jié)點(diǎn) 8(i = 0)，發(fā)現(xiàn)其本身已為根結(jié)點(diǎn)，沒有父結(jié)點(diǎn)，更新結(jié)束。

更新結(jié)點(diǎn)值的時(shí)間復(fù)雜度也為，即為樹高。

插入結(jié)點(diǎn) insert() ：插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度也為。將一個(gè)新結(jié)點(diǎn)插入到樹的末尾，如果新結(jié)點(diǎn)的值大于其父結(jié)點(diǎn)的值，插入就直接完成了;否則，類似于 updateKey() 操作，向上回溯修正堆。

void insert(int k)  
{  
    if (heap_size == capacity)  
    {  
        cout << "\n溢出：無法插入\n";  
        return;  
    }  
   
    // 將新插入的結(jié)點(diǎn)插入最后一個(gè)位置 heap_size - 1 
    heap_size++;  
    int i = heap_size - 1;  
    harr[i] = k;  
   
    // 如果違反堆的性質(zhì)，則向上回溯進(jìn)行修正 
    while (i != 0 && harr[parent(i)] > harr[i])  
    {  
       swap(&harr[i], &harr[parent(i)]);  
       i = parent(i);  
    }  
}

比如，我們插入結(jié)點(diǎn) 30(i = 5) ，由于其值大于父結(jié)點(diǎn)的值 20 ，并沒有違反堆的屬性，直接插入完成。

在插入結(jié)點(diǎn) 30 的基礎(chǔ)上，我們再插入結(jié)點(diǎn) 9(i = 6) ：

新插入結(jié)點(diǎn)的值 9(i = 6) 小于父結(jié)點(diǎn) 20(i = 2) 的值，故交換結(jié)點(diǎn) 9 和 20 ，然后繼續(xù)判斷值為 9(i = 2) ：

判斷結(jié)點(diǎn) 9(i = 2) 與其結(jié)點(diǎn) 10(i = 0) 的值， 9 < 10 ，交換 9 和 10 ，然后繼續(xù)判斷值9(i = 2) ：

發(fā)現(xiàn)值 9(i = 2) 已經(jīng)是根結(jié)點(diǎn)了，插入完成。

刪除結(jié)點(diǎn) delete() : 刪除一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度也是。將要刪除的結(jié)點(diǎn)用無窮小 INT_MIN 替換，即調(diào)用 updateKey(i, INT_MIN) ; 然后再將堆頂元素 INT_MIN 移除，即調(diào)用 removeMin() 。

void delete(int i)  
{  
    updateKey(i, INT_MIN);  
    removeMin();  
}

比如，我們刪除結(jié)點(diǎn) 15(i = 1) ，第一步，調(diào)用 update(1, INT_MIN) 將該結(jié)點(diǎn)的值替換為INT_MIN :

第二步：調(diào)用 removeMin() 函數(shù)將 INT_MIN 移除即可。

最后再來看一下 removeMin() 函數(shù)中提到的堆化操作的實(shí)現(xiàn)代碼(結(jié)合前面介紹removeMin() 函數(shù)時(shí)堆化的圖文)：

void Heapify(int i) 
{ 
    int l = left(i); //結(jié)點(diǎn) i 的左孩子下標(biāo) 2i + 1 
    int r = right(i); //結(jié)點(diǎn) i 的右孩子小標(biāo) 2i + 2 
    int samllest = i; 
    if(l < heap_size && arr[l] < arr[i]) 
    { 
     smallest = l;  
    } 
 if(r < heap_size && arr[r] < arr[smallest]) 
    { 
        smallest = r; 
    } 
     
    if(smallist != i) 
    { 
        swap(&arr[i], &arr[smallest]); 
        Heapify(smallest); 
    } 
}