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

創(chuàng)新互聯(lián)專(zhuān)業(yè)為企業(yè)提供射洪網(wǎng)站建設(shè)、射洪做網(wǎng)站、射洪網(wǎng)站設(shè)計(jì)、射洪網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、射洪企業(yè)網(wǎng)站模板建站服務(wù)，十載射洪做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

在正式開(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)中

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

網(wǎng)站題目：什么是二叉堆
標(biāo)題路徑：http://jinyejixie.com/article40/gpiheo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、服務(wù)器托管、品牌網(wǎng)站設(shè)計(jì)、建站公司、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站排名

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)