C語言每日一練 —— 第19天:二叉堆

前言

  在之前的文章 二叉搜索樹 中,對於 「 增 」「 刪 」「 改 」「 查 」 的時間復雜度為 O ( l o g 2 n ) O(log_2n) O(log2n) ~ O ( n ) O(n) O(n)。原因是最壞情況下,二叉搜索樹會退化成 「 線性表 」 。更加確切地說,樹的高度決定瞭它插入、刪除和查找的時間復雜度。
  本文,我們就來聊一下一種高度始終能夠接近 O ( l o g 2 n ) O(log_2n) O(log2n)「 樹形 」 的數據結構,它能夠在 O ( 1 ) O(1) O(1) 的時間內,獲得 關鍵字 最大(或者最小)的元素。並且能夠在 O ( l o g 2 n ) O(log_2n) O(log2n) 的時間內執行插入和刪除,一般用來做 優先隊列 的實現。它就是:

「 二叉堆 」

文章目錄

  • 前言
  • 一、堆的概念
    • 1、概述
    • 2、定義
    • 3、性質
    • 4、作用
  • 二、堆的存儲結構
    • 1、根結點編號
    • 2、孩子結點編號
    • 3、父結點編號
    • 4、數據域
    • 5、堆的數據結構
  • 三、堆的常用接口
    • 1、元素比較
    • 2、交換元素
    • 3、空判定
    • 4、滿判定
    • 5、上浮操作
    • 6、下沉操作
  • 四、堆的創建
    • 1、算法描述
    • 2、動畫演示
    • 3、源碼詳解
  • 五、堆元素的插入
    • 1、算法描述
    • 2、動畫演示
    • 3、源碼詳解
  • 五、堆元素的刪除
    • 1、算法描述
    • 2、動畫演示
    • 3、源碼詳解

一、堆的概念 1、概述

  堆是計算機科學中一類特殊的數據結構的統稱。實現有很多,例如:大頂堆,小頂堆,斐波那契堆,左偏堆,斜堆 等等。從子結點個數上可以分為二叉堆,N叉堆等等。本文將介紹的是 二叉堆。

2、定義

  二叉堆本質是一棵完全二叉樹,所以每次元素的插入刪除都能保證 O ( l o g 2 n ) O(log_2n) O(log2n)。根據堆的偏序規則,分為 小頂堆 和 大頂堆。小頂堆,顧名思義,根結點的關鍵字最小;大頂堆則相反。如圖所示,表示的是一個大頂堆。

3、性質

  以大頂堆為例,它總是滿足下列性質:
  1)空樹是一個大頂堆;
  2)大頂堆中某個結點的關鍵字 小於等於 其父結點的關鍵字;
  3)大頂堆是一棵完全二叉樹。有關完全二叉樹的內容,可以參考:畫解完全二叉樹。
如下圖所示,任意一個從葉子結點到根結點的路徑總是一個單調不降的序列。

  小頂堆隻要把上文中的 小於等於 替換成 大於等於 即可。

4、作用

  還是以大頂堆為例,堆能夠在 O ( 1 ) O(1) O(1) 的時間內,獲得 關鍵字 最大的元素。並且能夠在 O ( l o g 2 n ) O(log_2n) O(log2n) 的時間內執行插入和刪除。一般用來做 優先隊列 的實現。

二、堆的存儲結構

  學習堆的過程中,我們能夠學到一種新的表示形式。就是:利用 數組 來表示 鏈式結構。怎麼理解這句話呢?
  由於堆本身是一棵完全二叉樹,所以我們可以把每個結點,按照層序映射到一個順序存儲的數組中,然後利用每個結點在數組中的下標,來確定結點之間的關系。
  如圖所示,描述的是堆結點下標和結點之間的關系,結點上的數字代表的是 數組下標。從左往右按照層序進行連續遞增。

1、根結點編號

  根結點的編號,看作者的喜好。可以用 0 或者 1。本文的作者是 C語言 出身,所以更傾向於選擇 0 作為根結點的編號(因為用 1 作為根結點編號的話,數組的第 0 個元素就浪費瞭)。
  我們可以用一個宏定義來實現它的定義,如下:

#define root 0

2、孩子結點編號

  那麼,根結點的兩個左右子樹的編號,就分別為 1 和 2 瞭。以此類推,按照層序進行編號的話,1 的左右子樹編號為 3 和 4;2 的左右子樹編號為 5 和 6。
  根據數學歸納法,對於編號為 i i i 的結點,它的左子樹編號為 2 i + 1 2i+1 2i+1,右子樹編號為 2 i + 2 2i+2 2i+2。用宏定義實現如下:

#define lson(idx) (2*idx+1)#define rson(idx) (2*idx+2)

  由於這裡涉及到乘 2,所以我們還可以用左移位運算來優化乘法運算,如下:

#define lson(idx) (idx << 1|1)#define rson(idx) ((idx + 1) << 1)

3、父結點編號

  同樣,父結點編號也可以通過數學歸納法得出,當結點編號為 i i i 時,它的父結點編號為 i − 1 2 \frac {i-1} {2} 2i1,利用C語言實現如下:

#define parent(idx) ((idx - 1) / 2)

  這裡涉及到除 2,可以利用右移運算符進行優化,如下:

#define parent(idx) ((idx - 1) >> 1)

  這裡利用補碼的性質,根結點的父結點得到的值為 -1;

4、數據域

  堆數據元素的數據域可以定義兩個:關鍵字 和 值,其中關鍵字一般是整數,方便進行比較確定大小關系;值則是用於展示用,可以是任意類型,可以用typedef struct進行定義如下:

typedef struct {    int key;      // (1)    void *any;    // (2)}DataType;
  • ( 1 ) (1) (1) 關鍵字;
  • ( 2 ) (2) (2) 值,定義成一個空指針,可以用來表示任意類型;

5、堆的數據結構

  由於堆本質上是一棵完全二叉樹,所以將它一一映射到數組後,一定是連續的。我們可以用一個數組來代表一個堆,在C語言中的數組擁有一個固定長度,可以用一個Heap結構體表示如下:

typedef struct {    DataType *data;  // (1)    int size;        // (2)    int capacity;    // (3)}Heap;
  • ( 1 ) (1) (1) 堆元素所在數組的首地址;
  • ( 2 ) (2) (2) 堆元素個數;
  • ( 3 ) (3) (3) 堆的最大元素個數;

三、堆的常用接口 1、元素比較

  兩個堆元素的比較可以采用一個比較函數compareData來完成,比較過程就是對關鍵字key進行比較的過程,以大頂堆為例:
  a. 大於返回 -1,代表需要執行交換;
  b. 小於返回 1,代表需要執行交換;
  c. 等於返回 0,代表需要執行交換;

int compareData(const DataType* a, const DataType* b) {    if(a->key > b->key) {        return -1;    }else if(a->key < b->key) {        return 1;    }    return 0;}

2、交換元素

  交換兩個元素的位置,也是堆這種數據結構中很常見的操作,C語言實現也比較簡單,如下:

void swap(DataType* a, DataType* b) {    DataType tmp = *a;    *a = *b;    *b = tmp;}

  更加詳細的內容,可以參考:《算法零基礎100講》(第16講) 變量交換算法 這篇文章。

3、空判定

  空判定是一個查詢接口,即詢問堆是否是空的,實現如下:

bool HeapIsEmpty(Heap *heap) {    return heap->size == 0;}

4、滿判定

  滿判定是一個查詢接口,即詢問堆是否是滿的,實現如下:

bool heapIsFull(Heap *heap) {    return heap->size == heap->capacity;}

5、上浮操作

  對於大頂堆而言,從它葉子結點到根結點的元素關鍵字一定是單調不降的,如果某個元素出現瞭比它的父結點大的情況,就需要進行上浮操作。
  上浮操作就是對 當前結點父結點 進行比較,如果它的關鍵字比父結點大(compareData返回-1的情況),將它和父結點進行交換,繼續上浮操作;否則,終止上浮操作。
  如圖所示,代表的是一個關鍵字為 95 的結點,通過不斷上浮,到達根結點的過程。上浮完畢以後,它還是一個大頂堆。

  上浮過程的 C語言 實現如下:

void heapShiftUp(Heap* heap, int curr) {               // (1)    int par = parent(curr);                            // (2)    while(par >= root) {                               // (3)        if( compareData( &heap->data[curr], &heap->data[par] ) < 0 ) {            swap(&heap->data[curr], &heap->data[par]); // (4)             curr = par;            par = parent(curr);        }else {            break;                                     // (5)         }    }}
  • ( 1 ) (1) (1) heapShiftUp這個接口是一個內部接口,所以用小寫駝峰區分,用於實現對堆中元素進行插入的時候的上浮操作;
  • ( 2 ) (2) (2) curr表示需要進行上浮操作的結點在堆中的編號,par表示curr的父結點編號;
  • ( 3 ) (3) (3) 如果已經是根結點,則無須進行上浮操作;
  • ( 4 ) (4) (4) 子結點的關鍵字 大於 父結點的關鍵字,則執行交換,並且更新新的 當前結點 和 父結點編號;
  • ( 5 ) (5) (5) 否則,說明已經正確歸位,上浮操作結束,跳出循環;

6、下沉操作

  對於大頂堆而言,從它 根結點 到 葉子結點 的元素關鍵字一定是單調不增的,如果某個元素出現瞭比它的某個子結點小的情況,就需要進行下沉操作。
  下沉操作就是對 當前結點關鍵字相對較小的子結點 進行比較,如果它的關鍵字比子結點小,將它和這個子結點進行交換,繼續下沉操作;否則,終止下沉操作。
  如圖所示,代表的是一個關鍵字為 19 的結點,通過不斷下沉,到達葉子結點的過程。下沉完畢以後,它還是一個大頂堆。

  下沉過程的 C語言 實現如下:

void heapShiftDown(Heap* heap, int curr) {            // (1)    int son = lson(curr);                             // (2)    while(son < heap->size) {        if( rson(curr) < heap->size ) {            if( compareData( &heap->data[rson(curr)], &heap->data[son] ) < 0 ) {                son = rson(curr);                     // (3)             }                }        if( compareData( &heap->data[son], &heap->data[curr] ) < 0 ) {            swap(&heap->data[son], &heap->data[curr]); // (4)            curr = son;            son = lson(curr);        }else {            break;                                     // (5)         }    }}
  • ( 1 ) (1) (1) heapShiftDown這個接口是一個內部接口,所以用小寫駝峰區分,用於對堆中元素進行刪除的時候的下沉調整;
  • ( 2 ) (2) (2) curr表示需要進行下沉操作的結點在堆中的編號,son表示curr的左兒子結點編號;
  • ( 3 ) (3) (3) 始終選擇關鍵字更小的子結點;
  • ( 4 ) (4) (4) 子結點的值小於父結點,則執行交換;
  • ( 5 ) (5) (5) 否則,說明已經正確歸位,下沉操作結束,跳出循環;

四、堆的創建 1、算法描述

  通過給定的數據集合,創建堆。可以先創建堆數組的內存空間,然後一個一個執行堆的插入操作。插入操作的具體實現,會在下文繼續講解。

2、動畫演示

3、源碼詳解

Heap* HeapCreate(DataType *data, int dataSize, int maxSize) {    // (1)    int i;    Heap *h = (Heap *)malloc( sizeof(Heap) );                    // (2)    h->data = (DataType *)malloc( sizeof(DataType) * maxSize );  // (3)    h->size = 0;                                                 // (4)    h->capacity = maxSize;                                       // (5)    for(i = 0; i < dataSize; ++i) {        HeapPush(h, data[i]);                                    // (6)    }    return h;                                                    // (7)}
  • ( 1 ) (1) (1) 給定一個元素個數為dataSize的數組data,創建一個最大元素個數為maxSize的堆並返回堆的結構體指針;
  • ( 2 ) (2) (2) 利用malloc申請堆的結構體的內存;
  • ( 3 ) (3) (3) 利用malloc申請存儲堆數據的數組的內存空間;
  • ( 4 ) (4) (4) 初始化空堆;
  • ( 5 ) (5) (5) 初始化堆最大元素個數為maxSize
  • ( 6 ) (6) (6) 遍歷數組執行堆的插入操作,插入的具體實現HeapPush接下來會講到;
  • ( 7 ) (7) (7) 最後,返回堆的結構體指針;

五、堆元素的插入 1、算法描述

  堆元素的插入過程,就是先將元素插入堆數組的最後一個位置,然後執行上浮操作;

2、動畫演示

3、源碼詳解

bool HeapPush(Heap* heap, DataType data) {    if( heapIsFull(heap) ) {        return false;                  // (1)    }    heap->data[ heap->size++ ] = data; // (2)    heapShiftUp(heap, heap->size-1);   // (3)    return true;}
  • ( 1 ) (1) (1) 堆已滿,不能進行插入;
  • ( 2 ) (2) (2) 插入堆數組的最後一個位置;
  • ( 3 ) (3) (3) 對最後一個位置的 堆元素 執行上浮操作;

五、堆元素的刪除 1、算法描述

  堆元素的刪除,隻能對堆頂元素進行操作,可以將數組的最後一個元素放到堆頂,然後對堆頂元素進行下沉操作。

2、動畫演示

3、源碼詳解

bool HeapPop(Heap *heap) {    if(HeapIsEmpty(heap)) {        return false;                               // (1)    }    heap->data[root] = heap->data[ --heap->size ];  // (2)    heapShiftDown(heap, root);                      // (3)    return true;}
  • ( 1 ) (1) (1) 堆已空,無法執行刪除;
  • ( 2 ) (2) (2) 將堆數組的最後一個元素放入堆頂,相當於刪除瞭堆頂元素;
  • ( 3 ) (3) (3) 對堆頂元素執行下沉操作;

  

👇🏻 九日集訓 可通過下方 公眾號 參加👇🏻