[[339907]]

在正式開始學習堆之前，一定要大腦里回顧一下什么是完全二叉樹，因為它和堆可是息息相關奧!

如果二叉樹中除了葉子結點，每個結點的度都為 2，則此二叉樹稱為滿二叉樹。

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

 

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

 

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

當i>1時，父親結點為結點 。i/2時，i=1時，表示的是根結點，無父親結點);比如結點 45 的的標號為 4 ，其父結點 15 的標號為 2 ，而2=4/2 ;

如果2Xi >n(總結點的個數) ，則結點 肯定沒有左孩子(為葉子結點);否則其左孩子是結點2Xi 。比如結點 15 的標號為 2 ，其左孩子結點為 4 ;

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

堆堆(Heap)是一類基于完全二叉樹的特殊數據結構。通常將堆分為兩種類型：

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

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

 

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

二叉堆

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

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

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

 

這就是兩個典型的小頂堆。

二叉堆的存儲結構

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

數組表示含義

數組表示	含義
arr[(i-1)/2]	第 i 個結點的父結點
arr[2*i + 1]	第 i 個結點的左孩子結點
arr[2*i + 2]	第 i 個結點的右孩子結點

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

 

小頂二叉堆的常見操作

獲取小頂二叉堆的根元素 getMin() ，這一操作的時間復雜度為 ;按照上面的存儲結構，根結點為 arr[0] ，返回即可。

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

移除小頂二叉堆的最小元素 removeMin() ，這一操作的時間復雜度為 ，因為移除小頂二叉堆的最小元素(即堆頂元素)之后，需要對堆進行調整，從而使得堆依舊維持其屬性，一般將調整的過程稱為 堆化 (heapify)。

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

我們以下圖為例進行說明：

 

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

 

然后從堆頂元素 50 開始進行堆化。

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

 

第二步：計算當前要進行堆化的結點 50(i = 1) 的左右孩子，左孩子 ，右孩子不存在，比較 50 和 45 ，發現 50 > 45 ，交換兩者，然后繼續對值為 50 的頂點(i = 3)的子樹進行堆化：

 

第三步：計算要進行堆化的結點 50 (i = 1) 的左右孩子，發現不存在，所以結點 50 已經到葉子結點，整棵樹堆化完成啦(其實這個堆化的過程還是挺簡單的，我們后面刪除等還會用到堆化的，這里不明白，不影響下面繼續噠!)。

更新給定下標的值 updateKey(int i，int new_val) ，這里有一個假設是 new_val < val 的值，如果 new_val > val ，那么就是對更新的結點進行堆化啦，所以就不單獨進行處理。還想兩種都處理，加個 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);  
    }  
} 

這個操作和堆化的操作相反，我們是從被更新的結點開始向上回溯，直到結點的值大于父結點的值停止。

 

我們將下標為 4 的結點 50 的值更新為 8 ：

 

第一步：判斷結點 8(i = 4) 的父結點的大小關系，8 < 15 ，交換 8和 15 ，然后結點 8(i = 1) 繼續做判斷：

 

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

 

第三步：判斷結點 8(i = 0)，發現其本身已為根結點，沒有父結點，更新結束。

更新結點值的時間復雜度也為 ，即為樹高。

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

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

 

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

 

在插入結點 30 的基礎上，我們再插入結點 9(i = 6) ：

 

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

 

判斷結點 9(i = 2) 與其結點 10(i = 0) 的值， 9 < 10 ，交換 9 和 10 ，然后繼續判斷值9(i = 2) ：

 

發現值 9(i = 2) 已經是根結點了，插入完成。

刪除結點 delete() : 刪除一個結點的時間復雜度也是 。將要刪除的結點用無窮小 INT_MIN 替換，即調用 updateKey(i, INT_MIN) ; 然后再將堆頂元素 INT_MIN 移除，即調用 removeMin() 。

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

 

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

 

第二步：調用 removeMin() 函數將 INT_MIN 移除即可。

 

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

void Heapify(int i) 
{ 
    int l = left(i); //結點 i 的左孩子下標 2i + 1 
    int r = right(i); //結點 i 的右孩子小標 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); 
    } 
} 

關于二叉堆的基本操作就介紹完了，因為二叉堆不論在考試還是面試中是最常見的，所以建議一定要搞懂奧!

堆的應用

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

二、優先隊列(Priority Queue)：使用二叉堆，可以實現一個高效的優先隊列，因為二叉堆的各類操作的時間復雜度均為 。(優先隊列好像我沒講，以后有機會一定更新)

三、圖算法(Graph Algorithms)：優先隊列廣泛應用于像迪杰斯特拉算法和普里姆算法的圖算法當中

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

本文轉載自微信公眾號「景禹」，可以通過以下二維碼關注。轉載本文請聯系景禹公眾號