C語言每日練習之二叉堆

一、堆的概念

1、概述

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

2、定義

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

3、性質

以大頂堆為例,它總是滿足下列性質:
1)空樹是一個大頂堆;

2)大頂堆中某個結點的關鍵字 小於等於 其父結點的關鍵字;

3)大頂堆是一棵完全二叉樹。有關完全二叉樹的內容,可以參考:畫解完全二叉樹。

如下圖所示,任意一個從葉子結點到根結點的路徑總是一個單調不降的序列。

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

4、作用

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

二、堆的存儲結構

學習堆的過程中,我們能夠學到一種新的表示形式。就是:利用 數組 來表示 鏈式結構。怎麼理解這句話呢?

由於堆本身是一棵完全二叉樹,所以我們可以把每個結點,按照層序映射到一個順序存儲的數組中,然後利用每個結點在數組中的下標,來確定結點之間的關系。

如圖所示,描述的是堆結點下標和結點之間的關系,結點上的數字代表的是 數組下標。從左往右按照層序進行連續遞增。

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} 2i−1​,利用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) 關鍵字;
  • (2) 值,定義成一個空指針,可以用來表示任意類型;

5、堆的數據結構

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

typedef struct {
    DataType *data;  // (1)
    int size;        // (2)
    int capacity;    // (3)
}Heap;
  • (1) 堆元素所在數組的首地址;
  • (2) 堆元素個數;
  • (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;
}

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) heapShiftUp這個接口是一個內部接口,所以用小寫駝峰區分,用於實現對堆中元素進行插入的時候的上浮操作;

(2) curr表示需要進行上浮操作的結點在堆中的編號,par表示curr的父結點編號;

(3) 如果已經是根結點,則無須進行上浮操作;

(4) 子結點的關鍵字 大於 父結點的關鍵字,則執行交換,並且更新新的 當前結點 和 父結點編號;

(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)         }    }}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) heapShiftDown這個接口是一個內部接口,所以用小寫駝峰區分,用於對堆中元素進行刪除的時候的下沉調整;

(2) curr表示需要進行下沉操作的結點在堆中的編號,son表示curr的左兒子結點編號;

(3) 始終選擇關鍵字更小的子結點;

(4) 子結點的值小於父結點,則執行交換;

(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) 給定一個元素個數為dataSize的數組data,創建一個最大元素個數為maxSize的堆並返回堆的結構體指針;

(2) 利用malloc申請堆的結構體的內存;

(3) 利用malloc申請存儲堆數據的數組的內存空間;

(4) 初始化空堆;

(5) 初始化堆最大元素個數為maxSize

(6) 遍歷數組執行堆的插入操作,插入的具體實現HeapPush接下來會講到;

(7) 最後,返回堆的結構體指針;

五、堆元素的插入

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) 堆已滿,不能進行插入;

(2) 插入堆數組的最後一個位置;

(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) 堆已空,無法執行刪除;
  • (2) 將堆數組的最後一個元素放入堆頂,相當於刪除瞭堆頂元素;
  • (3) 對堆頂元素執行下沉操作;

總結

本篇文章就到這裡瞭,希望能夠給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!

推薦閱讀: