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

二叉堆是什麼鬼?

(給演演算法愛好者加星標,修煉程式設計內功

作者:帥地 (本文來自作者投稿,簡介見末尾)

二叉堆是一種應用很廣的資料結構,今天,我們就來簡單講講二叉堆。

什麼是二叉堆?

二叉堆是一種特殊的堆。具有如下的特性:

  1. 具有完全二叉樹的特性。

  2. 堆中的任何一個父節點的值都大於等於它左右孩子節點的值,或者都小於等於它左右孩子節點的值。

根據第二條特性,我們又可以把二叉堆分成兩類:

1、最大堆:父節點的值大於等於左右孩子節點的值。

2、最小堆:父節點的值小於等於左右孩子節點的值。

我們把二叉堆的根節點稱之為堆頂。根據二叉堆的特性,堆頂要嘛是整個堆中的最大元素,要嘛是最小元素

今天,我們主要來講講二叉堆的三個主要操作:

  1. 插入一個節點。

  2. 刪除一個節點。

  3. 構建一個二叉堆。

不過這裡需要註意的是,在二叉堆這種結構中,對於刪除一個節點,我們一般刪的是根節點

下麵我們以最小堆為例子,來講講這些操作。

插入一個節點。

剛才我們說二叉堆具有完全二叉樹的特性,因此,我們在插入一個節點的時候,應該先保證節點插入後,它仍然是一顆完全二叉樹,然後再來進行調整,使它滿足二叉堆的另一個特性。

所以,在插入的時候,我們把新節點插到完全二叉樹的最後一個位置。例如:

插入0。

之後我們再來進行調整,調整的原則是:讓新插入的節點與它的父節點進行比較,如果新節點小於父節點,則讓新節點上浮,即和父節點交換位置。

上浮之後繼續和它的父節點進行比較,直到父節點的值小於或等於該節點,才停止上浮,即插入結束。例如:

0比5小,上浮。

0比2小於,上浮。

0比1小,上浮。

已經到達堆頂了,插入結束。

刪除節點。

前面說了,刪除節點一般刪除的是根節點。

和插入一樣,由於二叉堆具有完全二叉樹的特性,因為刪除時候,首先我們是要馬上恢復它具有完全二叉樹的特性,所以我們是採取這樣的策略:把根節點刪除之後,用二叉堆的最後一個元素頂替上來,然後在進行調整恢復。例如:

把0刪除了之後,5替換上來。

之後再來調整,調整的規則和插入差不多類似,採取下沉的策略:讓5和左右孩子節點相比較,如果左右節點有小於5的,則讓那個較小的孩子代替5的位置,然後5下沉。

下沉之後,5繼續和左右孩子相比,直到左右孩子都大於或等於5才結束。

如:5比1,3都大,1代替5的位置

5比4,2都大,2代替5的位置。

5已經不在具有左右孩子了,刪除結束。

構建二叉堆

所謂構建,就是給你一個有n個節點的無序的完全二叉樹,然後把它構建成二叉堆。

剛才我們在刪除一個節點的時候,把最後一個元素補到根元素的位置上去,然後再讓這個元素依次下沉,實際上,在這個元素還沒有下沉之前,它就可以看作是一顆無序的完全二叉樹了

也就是說,要把一個無序的完全二叉樹調整為二叉堆,我們可以讓所有非葉子節點依次下沉。不過下沉的順序不是從根節點開始下沉(想一下相必你就 知道不能從根節點開始下沉),而是從下麵的非葉子節點下稱,在依次往上。舉個例子:

對於這樣一顆無序的完全二叉樹

8進行下沉。

接著,5進行下沉。

2沒問題,之後讓7進行下沉

調整完成,構建結束。

程式碼實現

不過這裡需要說明的是,我們二叉樹一般是採用連結串列的方式來實現的,但二叉堆我們是採用陣列的方式來儲存的。

如果知道了一個節點的位置,如何知道一個節點的左右孩子節點的位置呢?

這其實不難,根據完全二叉樹的特點,假如一個節點的下標為n,則可以求得它左孩子的下標為:2 n+1;右孩子下標為:2 n+2。

下麵是構建程式碼的實現:

public class BinaryHeap {

   /**上浮操作,對插入的節點進行上浮
    *
    * @param arr
    * @param length :表示二叉堆的長度
    */

   public static int[] upAdjust(int arr[], int length){
       //標記插入的節點
       int child = length - 1;
       //其父親節點
       int parent = (child - 1)/2;
       //把插入的節點臨時儲存起來
       int temp = arr[child];

       //進行上浮
       while (child > 0 && temp < arr[parent]) {
           //其實不用進行每次都進行交換,單向賦值就可以了
           //當temp找到正確的位置之後,我們再把temp的值賦給這個節點
           arr[child] = arr[parent];
           child = parent;
           parent = (child - 1) / 2;
       }
       //退出迴圈代表找到正確的位置
       arr[child] = temp;
       return arr;
   }

   /**

    */


   /**
    *  下沉操作,執行刪除操作相當於把最後
    *  * 一個元素賦給根元素之後,然後對根元素執行下沉操作
    * @param arr
    * @param parent 要下沉元素的下標
    * @param length 陣列長度
    */

   public static int[] downAdjust(int[] arr, int parent, int length{
       //臨時保證要下沉的元素
       int temp = arr[parent];
       //定位左孩子節點位置
       int child = 2 * parent + 1;
       //開始下沉
       while (child < length) {
           //如果右孩子節點比左孩子小,則定位到右孩子
           if (child + 1 < length && arr[child] > arr[child + 1]) {
               child++;
           }
           //如果父節點比孩子節點小或等於,則下沉結束
           if (temp <= arr[child])
               break;
           //單向賦值
           arr[parent] = arr[child];
           parent = child;
           child = 2 * parent + 1;
       }
       arr[parent] = temp;
       return arr;
   }

   /**
    * 構建操作
    *
    * @param arr
    */

   public static int[] buildHead(int[] arr,int length{
       //從最後一個非葉子節點開始下沉
       for (int i = (length - 2) / 2; i >= 0; i--) {
           arr = downAdjust(arr, i, length);
       }
       return arr;
   }
}

 

本次講解到此結束。下篇繼續講解和堆有關的知識點。至於bitmap演演算法最佳化的那篇,會在之後給出。

【本文作者】

帥地:一個熱愛程式設計的在校生,我的世界不只有coding,還有writing。目前維護訂閱號「苦逼的碼農」,專註於寫計算機網路,資料結構等相關文章。

 

推薦閱讀

(點選標題可跳轉閱讀)

漫畫:什麼是堆排序?

詳解二叉堆及其實現

漫畫:什麼是二叉堆?

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

關註「演演算法愛好者」加星標,修煉程式設計內功

    贊(0)

    分享創造快樂