轉載自??漫畫：什么是二叉堆？（修正版）

?

?

?

什么是二叉堆？

二叉堆本質上是一種完全二叉樹，它分為兩個類型：

1.最大堆

2.最小堆

什么是最大堆呢？最大堆任何一個父節點的值，都大于等于它左右孩子節點的值。

?

什么是最小堆呢？最小堆任何一個父節點的值，都小于等于它左右孩子節點的值。

?

二叉堆的根節點叫做堆頂。

最大堆和最小堆的特點，決定了在最大堆的堆頂是整個堆中的最大元素；最小堆的堆頂是整個堆中的最小元素。

?

?

堆的自我調整

對于二叉堆，如下有幾種操作：

插入節點

刪除節點

構建二叉堆

這幾種操作都是基于堆的自我調整。

下面讓我們以最小堆為例，看一看二叉堆是如何進行自我調整的。

1.插入節點

二叉堆的節點插入，插入位置是完全二叉樹的最后一個位置。比如我們插入一個新節點，值是 0。

?

這時候，我們讓節點0的它的父節點5做比較，如果0小于5，則讓新節點“上浮”，和父節點交換位置。

?

繼續用節點0和父節點3做比較，如果0小于3，則讓新節點繼續“上浮”。

?

繼續比較，最終讓新節點0上浮到了堆頂位置。

2.刪除節點

?

二叉堆的節點刪除過程和插入過程正好相反，所刪除的是處于堆頂的節點。比如我們刪除最小堆的堆頂節點1。

?

這時候，為了維持完全二叉樹的結構，我們把堆的最后一個節點10補到原本堆頂的位置。

?

接下來我們讓移動到堆頂的節點10和它的左右孩子進行比較，如果左右孩子中最小的一個（顯然是節點2）比節點10小，那么讓節點10“下沉”。

繼續讓節點10和它的左右孩子做比較，左右孩子中最小的是節點7，由于10大于7，讓節點10繼續“下沉”。

?

這樣一來，二叉堆重新得到了調整。

3.構建二叉堆

構建二叉堆，也就是把一個無序的完全二叉樹調整為二叉堆，本質上就是讓所有非葉子節點依次下沉。

我們舉一個無序完全二叉樹的例子：

首先，我們從最后一個非葉子節點開始，也就是從節點10開始。如果節點10大于它左右孩子中最小的一個，則節點10下沉。

接下來輪到節點3，如果節點3大于它左右孩子中最小的一個，則節點3下沉。

接下來輪到節點1，如果節點1大于它左右孩子中最小的一個，則節點1下沉。事實上節點1小于它的左右孩子，所以不用改變。

接下來輪到節點7，如果節點7大于它左右孩子中最小的一個，則節點7下沉。

節點7繼續比較，繼續下沉。

這樣一來，一顆無序的完全二叉樹就構建成了一個最小堆。

?

?

堆的代碼實現

在擼代碼之前，我們還需要明確一點：

二叉堆雖然是一顆完全二叉樹，但它的存儲方式并不是鏈式存儲，而是順序存儲。換句話說，二叉堆的所有節點都存儲在數組當中。

數組中，在沒有左右指針的情況下，如何定位到一個父節點的左孩子和右孩子呢？

像圖中那樣，我們可以依靠數組下標來計算。

假設父節點的下標是parent，那么它的左孩子下標就是?2*parent+1；它的右孩子下標就是??2*parent+2?。

比如上面例子中，節點6包含9和10兩個孩子，節點6在數組中的下標是3，節點9在數組中的下標是7，節點10在數組中的下標是8。

7 = 3*2+1

8 = 3*2+2

剛好符合規律。

有了這個前提，下面的代碼就更好理解了：

public class HeapOperator { /** * 上浮調整 * @param array ? ? 待調整的堆 */public static void upAdjust(int[] array) {int childIndex = array.length-1;int parentIndex = (childIndex-1)/2;// temp保存插入的葉子節點值，用于最后的賦值int temp = array[childIndex];while (childIndex > 0 && temp < array[parentIndex]){//無需真正交換，單向賦值即可array[childIndex] = array[parentIndex];childIndex = parentIndex;parentIndex = (parentIndex-1) / 2;}array[childIndex] = temp; }/** * 下沉調整 * @param array ? ? 待調整的堆 * @param parentIndex ? ?要下沉的父節點 * @param parentIndex ? ?堆的有效大小 */ public static void downAdjust(int[] array, int parentIndex, int length) {// temp保存父節點值，用于最后的賦值int temp = array[parentIndex];int childIndex = 2 * parentIndex + 1;while (childIndex < length) {// 如果有右孩子，且右孩子小于左孩子的值，則定位到右孩子if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {childIndex++;}// 如果父節點小于任何一個孩子的值，直接跳出if (temp <= array[childIndex])break;//無需真正交換，單向賦值即可array[parentIndex] = array[childIndex];parentIndex = childIndex;childIndex = 2 * childIndex + 1;}array[parentIndex] = temp; }/** * 構建堆 * @param array ? ? 待調整的堆 */ public static void buildHeap(int[] array) {// 從最后一個非葉子節點開始，依次下沉調整for (int i = array.length / 2; i >= 0; i--) {downAdjust(array, i, array.length - 1);} }public static void main(String[] args) {int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};upAdjust(array);System.out.println(Arrays.toString(array));array = new int[] {7,1,3,10,5,2,8,9,6};buildHeap(array);System.out.println(Arrays.toString(array)); } }

代碼中有一個優化的點，就是父節點和孩子節點做連續交換時，并不一定要真的交換，只需要先把交換一方的值存入temp變量，做單向覆蓋，循環結束后，再把temp的值存入交換后的最終位置。

?

?

?

?

?

總結

以上是生活随笔為你收集整理的漫画：什么是二叉堆？（修正版）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。