歡迎光臨
每天分享高質量文章

漫畫:什麼是二叉堆?

(點擊上方公眾號,可快速關註)


來源:程式員小灰





—————  第二天  —————














————————————







什麼是二叉堆?


二叉堆本質上是一種完全二叉樹,它分為兩個型別:

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 {

  1. /**

  2. * 上浮調整

  3. * @param array     待調整的堆

  4. */

  5. public static void upAdjust(int[] array) {

  6.    int childIndex = array.length-1;

  7.    int parentIndex = (childIndex-1)/2;

  8.    // temp儲存插入的葉子節點值,用於最後的賦值

  9.    int temp = array[childIndex];

  10.    while (childIndex > 0 && temp < array[parentIndex])

  11.    {

  12.        //無需真正交換,單向賦值即可

  13.        array[childIndex] = array[parentIndex];

  14.        childIndex = parentIndex;

  15.        parentIndex = (parentIndex-1) / 2;

  16.    }

  17.    array[childIndex] = temp;

  18. }


  19. /**

  20. * 下沉調整

  21. * @param array     待調整的堆

  22. * @param parentIndex    要下沉的父節點

  23. * @param parentIndex    堆的有效大小

  24. */

  25. public static void downAdjust(int[] array, int parentIndex, int length) {

  26.    // temp儲存父節點值,用於最後的賦值

  27.    int temp = array[parentIndex];

  28.    int childIndex = 2 * parentIndex + 1;

  29.    while (childIndex < length) {

  30.        // 如果有右孩子,且右孩子小於左孩子的值,則定位到右孩子

  31.        if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {

  32.            childIndex++;

  33.        }

  34.        // 如果父節點小於任何一個孩子的值,直接跳出

  35.        if (temp <= array[childIndex])

  36.            break;

  37.        //無需真正交換,單向賦值即可

  38.        array[parentIndex] = array[childIndex];

  39.        parentIndex = childIndex;

  40.        childIndex = 2 * childIndex + 1;

  41.    }

  42.    array[parentIndex] = temp;

  43. }


  44. /**

  45. * 構建堆

  46. * @param array     待調整的堆

  47. */

  48. public static void buildHeap(int[] array) {

  49.    // 從最後一個非葉子節點開始,依次下沉調整

  50.    for (int i = array.length / 2; i >= 0; i--) {

  51.        downAdjust(array, i, array.length - 1);

  52.    }

  53. }


  54. public static void main(String[] args) {

  55.    int[] array = new int[] {1,3,2,6,5,7,8,9,10,0};

  56.    upAdjust(array);

  57.    System.out.println(Arrays.toString(array));

  58.    array = new int[] {7,1,3,10,5,2,8,9,6};

  59.    buildHeap(array);

  60.    System.out.println(Arrays.toString(array));

  61. }

}

代碼中有一個優化的點,就是父節點和孩子節點做連續交換時,並不一定要真的交換,只需要先把交換一方的值存入temp變數,做單向改寫,迴圈結束後,再把temp的值存入交換後的最終位置。








幾點補充:


本漫畫純屬娛樂,還請大家儘量珍惜當下的工作,切勿模仿。

【關於投稿】


如果大家有原創好文投稿,請直接給公號發送留言。


① 留言格式:
【投稿】+《 文章標題》+ 文章鏈接

② 示例:
【投稿】
《不要自稱是程式員,我十多年的 IT 職場總結》:

http://blog.jobbole.com/94148/


③ 最後請附上您的個人簡介哈~



覺得本文有幫助?請分享給更多人

關註「演算法愛好者」,修煉編程內功

赞(0)

分享創造快樂

© 2020 知識星球   网站地图