什么是二叉堆

本篇內(nèi)容介紹了“什么是二叉堆”的有關(guān)知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

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

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

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

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

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

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

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

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

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

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

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

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

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

二叉堆

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

1. 二叉堆必定是一顆完全二叉樹。二叉堆的此屬性也決定了他們適合存儲在數(shù)組當(dāng)中。

2. 二叉堆要么是小頂堆，要么是大頂堆。小頂二叉堆中的根結(jié)點的值是整棵樹中的最小值，而且二叉樹中的所有頂點及其子樹均滿足這一特性。大頂堆與小頂堆類似，大頂堆的根結(jié)點的值是整棵樹中的最大值，而且二叉樹中所有結(jié)點的值也均大于等于其子樹結(jié)點。

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

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

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

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

數(shù)組表示含義

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

小頂二叉堆的常見操作

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

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

移除小頂二叉堆的最小元素 removeMin() ，這一操作的時間復(fù)雜度為  ，因為移除小頂二叉堆的最小元素(即堆頂元素)之后，需要對堆進(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)前的堆頂元素），將堆中的最后一個元素放到堆頂，然后進(jìn)行Heapify()     int root = harr[0];      harr[0] = harr[heap_size-1];      heap_size--;      MinHeapify(0);         return root;  }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

void insert(int k)  {      if (heap_size == capacity)      {          cout << "\n溢出：無法插入\n";          return;      }         // 將新插入的結(jié)點插入最后一個位置 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é)點 30(i = 5) ，由于其值大于父結(jié)點的值 20 ，并沒有違反堆的屬性，直接插入完成。

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

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

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

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

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

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

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

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

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

void Heapify(int i) {     int l = left(i); //結(jié)點 i 的左孩子下標(biāo) 2i + 1     int r = right(i); //結(jié)點 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īng)用

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

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

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

“什么是二叉堆”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實用文章！