[[339907]]

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

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

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

 

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

 

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

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

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

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

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

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

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

 

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

二叉堆

二叉堆是滿(mǎn)足下面屬性的一顆二叉樹(shù)：

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

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

 

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

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

二叉堆是一顆完全二叉樹(shù)，一般用數(shù)組表示。其中根元素用 arr[0] 表示，而其他結(jié)點(diǎn)(第i 個(gè)結(jié)點(diǎn)的存儲(chǔ)位置)滿(mǎ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ì)上與一顆完全二叉樹(shù)自身所具有的特性一一對(duì)應(yīng)。

 

小頂二叉堆的常見(jiàn)操作

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

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

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

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

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

 

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

 

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

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

 

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

 

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

更新給定下標(biāo)的值 updateKey(int i，int new_val) ，這里有一個(gè)假設(shè)是 new_val < val 的值，如果 new_val > val ，那么就是對(duì)更新的結(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)開(kāi)始向上回溯，直到結(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)，沒(méi)有父結(jié)點(diǎn)，更新結(jié)束。

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

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

void insert(int k)  
{  
    if (heap_size == capacity)  
    {  
        cout << "\n溢出：無(wú)法插入\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 ，并沒(méi)有違反堆的屬性，直接插入完成。

 

在插入結(jié)點(diǎn) 30 的基礎(chǔ)上，我們?cè)俨迦虢Y(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ǎng)h除的結(jié)點(diǎn)用無(wú)窮小 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 移除即可。

 

最后再來(lái)看一下 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); 
    } 
} 

關(guān)于二叉堆的基本操作就介紹完了，因?yàn)槎娑巡徽撛诳荚囘€是面試中是最常見(jiàn)的，所以建議一定要搞懂奧!

堆的應(yīng)用

一、堆排序(Heap Sort)：堆排序可以使用二叉堆在 的時(shí)間內(nèi)對(duì)數(shù)組完成排序，這也是今天先講二叉堆的原因。

二、優(yōu)先隊(duì)列(Priority Queue)：使用二叉堆，可以實(shí)現(xiàn)一個(gè)高效的優(yōu)先隊(duì)列，因?yàn)槎娑训母黝?lèi)操作的時(shí)間復(fù)雜度均為 。(優(yōu)先隊(duì)列好像我沒(méi)講，以后有機(jī)會(huì)一定更新)

三、圖算法(Graph Algorithms)：優(yōu)先隊(duì)列廣泛應(yīng)用于像迪杰斯特拉算法和普里姆算法的圖算法當(dāng)中

除了講的二叉堆，還有基于二叉堆的變體，二項(xiàng)式堆、斐波那契堆等等，我們之后有余力了再一起學(xué)，現(xiàn)在還是 “功利” 一點(diǎn)兒，搞好我們考試和面試中最重要的二叉堆，周末愉快~~

本文轉(zhuǎn)載自微信公眾號(hào)「景禹」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系景禹公眾號(hào)