C語言每日練習之二叉堆
一、堆的概念
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} 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的更多內容!