C語言每日練習之二叉堆
一、堆的概念
1、概述
堆是計算機科學中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。實現(xiàn)有很多，例如：大頂堆，小頂堆，斐波那契堆，左偏堆，斜堆 等等。從子結(jié)點個數(shù)上可以分為二叉堆，N叉堆等等。本文將介紹的是 二叉堆。
2、定義
二叉堆本質(zhì)是一棵完全二叉樹，所以每次元素的插入刪除都能保證 O ( l o g 2 n ) O(log_2n) O(log2?n)。根據(jù)堆的偏序規(guī)則，分為 小頂堆 和 大頂堆。小頂堆，顧名思義，根結(jié)點的關(guān)鍵字最??；大頂堆則相反。如圖所示，表示的是一個大頂堆。
3、性質(zhì)
以大頂堆為例，它總是滿足下列性質(zhì)：
1）空樹是一個大頂堆；
2）大頂堆中某個結(jié)點的關(guān)鍵字 小于等于 其父結(jié)點的關(guān)鍵字；
3）大頂堆是一棵完全二叉樹。有關(guān)完全二叉樹的內(nèi)容，可以參考：畫解完全二叉樹。
如下圖所示，任意一個從葉子結(jié)點到根結(jié)點的路徑總是一個單調(diào)不降的序列。
小頂堆只要把上文中的 小于等于 替換成 大于等于 即可。
4、作用
還是以大頂堆為例，堆能夠在 O ( 1 ) O(1) O(1) 的時間內(nèi)，獲得 關(guān)鍵字 最大的元素。并且能夠在 O ( l o g 2 n ) O(log_2n) O(log2?n) 的時間內(nèi)執(zhí)行插入和刪除。一般用來做 優(yōu)先隊列 的實現(xiàn)。
二、堆的存儲結(jié)構(gòu)
學習堆的過程中，我們能夠?qū)W到一種新的表示形式。就是：利用 數(shù)組 來表示 鏈式結(jié)構(gòu)。怎么理解這句話呢？
由于堆本身是一棵完全二叉樹，所以我們可以把每個結(jié)點，按照層序映射到一個順序存儲的數(shù)組中，然后利用每個結(jié)點在數(shù)組中的下標，來確定結(jié)點之間的關(guān)系。
如圖所示，描述的是堆結(jié)點下標和結(jié)點之間的關(guān)系，結(jié)點上的數(shù)字代表的是 數(shù)組下標。從左往右按照層序進行連續(xù)遞增。
1、根結(jié)點編號
根結(jié)點的編號，看作者的喜好?？梢杂?0 或者 1。本文的作者是 C語言 出身，所以更傾向于選擇 0 作為根結(jié)點的編號（因為用 1 作為根結(jié)點編號的話，數(shù)組的第 0 個元素就浪費了）。
我們可以用一個宏定義來實現(xiàn)它的定義，如下：
#define root 0
2、孩子結(jié)點編號
那么，根結(jié)點的兩個左右子樹的編號，就分別為 1 和 2 了。以此類推，按照層序進行編號的話，1 的左右子樹編號為 3 和 4；2 的左右子樹編號為 5 和 6。
根據(jù)數(shù)學歸納法，對于編號為 i i i 的結(jié)點，它的左子樹編號為 2 i + 1 2i+1 2i+1，右子樹編號為 2 i + 2 2i+2 2i+2。用宏定義實現(xiàn)如下：
#define lson(idx) (2*idx+1) #define rson(idx) (2*idx+2)
由于這里涉及到乘 2，所以我們還可以用左移位運算來優(yōu)化乘法運算，如下：
#define lson(idx) (idx << 1|1) #define rson(idx) ((idx + 1) << 1)
3、父結(jié)點編號
同樣，父結(jié)點編號也可以通過數(shù)學歸納法得出，當結(jié)點編號為 i i i 時，它的父結(jié)點編號為 i − 1 2 \frac {i-1} {2} 2i−1?，利用C語言實現(xiàn)如下：
#define parent(idx) ((idx - 1) / 2)
這里涉及到除 2，可以利用右移運算符進行優(yōu)化，如下：
#define parent(idx) ((idx - 1) >> 1)
這里利用補碼的性質(zhì)，根結(jié)點的父結(jié)點得到的值為 -1；
4、數(shù)據(jù)域
堆數(shù)據(jù)元素的數(shù)據(jù)域可以定義兩個：關(guān)鍵字 和 值，其中關(guān)鍵字一般是整數(shù)，方便進行比較確定大小關(guān)系；值則是用于展示用，可以是任意類型，可以用typedef struct進行定義如下：
typedef struct {
int key; // (1)
void *any; // (2)
}DataType;
- (1) 關(guān)鍵字；
- (2) 值，定義成一個空指針，可以用來表示任意類型；
5、堆的數(shù)據(jù)結(jié)構(gòu)
由于堆本質(zhì)上是一棵完全二叉樹，所以將它一一映射到數(shù)組后，一定是連續(xù)的。我們可以用一個數(shù)組來代表一個堆，在C語言中的數(shù)組擁有一個固定長度，可以用一個Heap結(jié)構(gòu)體表示如下：
typedef struct {
DataType *data; // (1)
int size; // (2)
int capacity; // (3)
}Heap;
- (1) 堆元素所在數(shù)組的首地址；
- (2) 堆元素個數(shù)；
- (3) 堆的最大元素個數(shù)；
三、堆的常用接口
1、元素比較
兩個堆元素的比較可以采用一個比較函數(shù)compareData來完成，比較過程就是對關(guān)鍵字key進行比較的過程，以大頂堆為例：
a. 大于返回 -1，代表需要執(zhí)行交換；
b. 小于返回 1，代表需要執(zhí)行交換；
c. 等于返回 0，代表需要執(zhí)行交換；
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、交換元素
交換兩個元素的位置，也是堆這種數(shù)據(jù)結(jié)構(gòu)中很常見的操作，C語言實現(xiàn)也比較簡單，如下：
void swap(DataType* a, DataType* b) {
DataType tmp = *a;
*a = *b;
*b = tmp;
}
3、空判定
空判定是一個查詢接口，即詢問堆是否是空的，實現(xiàn)如下：
bool HeapIsEmpty(Heap *heap) {
return heap->size == 0;
}
4、滿判定
滿判定是一個查詢接口，即詢問堆是否是滿的，實現(xiàn)如下：
bool heapIsFull(Heap *heap) {
return heap->size == heap->capacity;
}
5、上浮操作
對于大頂堆而言，從它葉子結(jié)點到根結(jié)點的元素關(guān)鍵字一定是單調(diào)不降的，如果某個元素出現(xiàn)了比它的父結(jié)點大的情況，就需要進行上浮操作。
上浮操作就是對 當前結(jié)點 和 父結(jié)點 進行比較，如果它的關(guān)鍵字比父結(jié)點大（compareData返回-1的情況），將它和父結(jié)點進行交換，繼續(xù)上浮操作；否則，終止上浮操作。
如圖所示，代表的是一個關(guān)鍵字為 95 的結(jié)點，通過不斷上浮，到達根結(jié)點的過程。上浮完畢以后，它還是一個大頂堆。
上浮過程的 C語言 實現(xiàn)如下：
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這個接口是一個內(nèi)部接口，所以用小寫駝峰區(qū)分，用于實現(xiàn)對堆中元素進行插入的時候的上浮操作；
(2) curr表示需要進行上浮操作的結(jié)點在堆中的編號，par表示curr的父結(jié)點編號；
(3) 如果已經(jīng)是根結(jié)點，則無須進行上浮操作；
(4) 子結(jié)點的關(guān)鍵字 大于 父結(jié)點的關(guān)鍵字，則執(zhí)行交換，并且更新新的 當前結(jié)點 和 父結(jié)點編號；
(5) 否則，說明已經(jīng)正確歸位，上浮操作結(jié)束，跳出循環(huán)；
6、下沉操作
對于大頂堆而言，從它 根結(jié)點 到 葉子結(jié)點 的元素關(guān)鍵字一定是單調(diào)不增的，如果某個元素出現(xiàn)了比它的某個子結(jié)點小的情況，就需要進行下沉操作。
下沉操作就是對 當前結(jié)點 和 關(guān)鍵字相對較小的子結(jié)點 進行比較，如果它的關(guān)鍵字比子結(jié)點小，將它和這個子結(jié)點進行交換，繼續(xù)下沉操作；否則，終止下沉操作。
如圖所示，代表的是一個關(guān)鍵字為 19 的結(jié)點，通過不斷下沉，到達葉子結(jié)點的過程。下沉完畢以后，它還是一個大頂堆。
下沉過程的 C語言 實現(xiàn)如下：
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這個接口是一個內(nèi)部接口，所以用小寫駝峰區(qū)分，用于對堆中元素進行刪除的時候的下沉調(diào)整；
(2) curr表示需要進行下沉操作的結(jié)點在堆中的編號，son表示curr的左兒子結(jié)點編號；
(3) 始終選擇關(guān)鍵字更小的子結(jié)點；
(4) 子結(jié)點的值小于父結(jié)點，則執(zhí)行交換；
(5) 否則，說明已經(jīng)正確歸位，下沉操作結(jié)束，跳出循環(huán)；
四、堆的創(chuàng)建
1、算法描述
通過給定的數(shù)據(jù)集合，創(chuàng)建堆。可以先創(chuàng)建堆數(shù)組的內(nèi)存空間，然后一個一個執(zhí)行堆的插入操作。插入操作的具體實現(xiàn)，會在下文繼續(xù)講解。
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) 給定一個元素個數(shù)為dataSize的數(shù)組data，創(chuàng)建一個最大元素個數(shù)為maxSize的堆并返回堆的結(jié)構(gòu)體指針；
(2) 利用malloc申請堆的結(jié)構(gòu)體的內(nèi)存；
(3) 利用malloc申請存儲堆數(shù)據(jù)的數(shù)組的內(nèi)存空間；
(4) 初始化空堆；
(5) 初始化堆最大元素個數(shù)為maxSize；
(6) 遍歷數(shù)組執(zhí)行堆的插入操作，插入的具體實現(xiàn)HeapPush接下來會講到；
(7) 最后，返回堆的結(jié)構(gòu)體指針；
五、堆元素的插入
1、算法描述
堆元素的插入過程，就是先將元素插入堆數(shù)組的最后一個位置，然后執(zhí)行上浮操作；
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) 插入堆數(shù)組的最后一個位置；
(3) 對最后一個位置的 堆元素 執(zhí)行上浮操作；
五、堆元素的刪除
1、算法描述
堆元素的刪除，只能對堆頂元素進行操作，可以將數(shù)組的最后一個元素放到堆頂，然后對堆頂元素進行下沉操作。
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) 堆已空，無法執(zhí)行刪除；
- (2) 將堆數(shù)組的最后一個元素放入堆頂，相當于刪除了堆頂元素；
- (3) 對堆頂元素執(zhí)行下沉操作；
總結(jié)
本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!
相關(guān)文章
這篇文章主要為大家詳細介紹了C++的原生數(shù)組，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
C++?Boost?MultiArray簡化使用多維數(shù)組庫
Boost是為C++語言標準庫提供擴展的一些C++程序庫的總稱。Boost庫是一個可移植、提供源代碼的C++庫，作為標準庫的后備，是C++標準化進程的開發(fā)引擎之一，是為C++語言標準庫提供擴展的一些C++程序庫的總稱2022-11-11
掃雷是電腦上很經(jīng)典很經(jīng)典的傳統(tǒng)老游戲，從小編第一次摸到計算機開始就玩過掃雷，雖然當時并不理解玩法原理，但終是第一次玩電腦游戲，下面來從掃雷的前世今生講起2021-11-11
CMake是一個跨平臺的安裝/編譯工具,通過CMake我們可以通過簡單的語句來描述所有平臺的安裝/編譯過程,下面這篇文章主要給大家介紹了關(guān)于cmake跨平臺構(gòu)建工具的相關(guān)資料,需要的朋友可以參考下2023-02-02
深入了解C++ 結(jié)構(gòu)體（struct）與共用體（union）
這篇文章主要介紹了C++ 結(jié)構(gòu)體與共用體的的相關(guān)資料，幫助大家更好的理解和學習c++，感興趣的朋友可以了解下2020-08-08
C++語法詳解之封裝、構(gòu)造函數(shù)、析構(gòu)函數(shù)
這篇文章主要介紹了C++語法詳解之封裝、構(gòu)造函數(shù)、析構(gòu)函數(shù)的相關(guān)知識，通過實例代碼給大家詳細介紹，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2020-03-03
本文詳細講解了七大經(jīng)典排序算法,文中通過示例代碼介紹的非常詳細。對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-12-12
野指針和懸空指針是指針中常見的兩個概念，本文詳細的介紹了這兩種的使用，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-08-08
本文主要介紹了C++實現(xiàn)list增刪查改模擬,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2023-12-12
以下是對C++中的的sstream標準庫進行了詳細的介紹，需要的朋友可以過來參考下2013-09-09