一、堆的概念

1、概述

堆是計(jì)算機(jī)科學(xué)中一類特殊的數(shù)據(jù)結(jié)構(gòu)的統(tǒng)稱。實(shí)現(xiàn)有很多，例如：大頂堆，小頂堆，斐波那契堆，左偏堆，斜堆 等等。從子結(jié)點(diǎn)個(gè)數(shù)上可以分為二叉堆，N叉堆等等。本文將介紹的是 二叉堆。

2、定義

二叉堆本質(zhì)是一棵完全二叉樹，所以每次元素的插入刪除都能保證 O ( l o g 2 n ) O(log_2n) O(log2?n)。根據(jù)堆的偏序規(guī)則，分為 小頂堆 和 大頂堆。小頂堆，顧名思義，根結(jié)點(diǎn)的關(guān)鍵字最??；大頂堆則相反。如圖所示，表示的是一個(gè)大頂堆。

3、性質(zhì)

以大頂堆為例，它總是滿足下列性質(zhì)：
1）空樹是一個(gè)大頂堆；

2）大頂堆中某個(gè)結(jié)點(diǎn)的關(guān)鍵字 小于等于 其父結(jié)點(diǎn)的關(guān)鍵字；

3）大頂堆是一棵完全二叉樹。有關(guān)完全二叉樹的內(nèi)容，可以參考：畫解完全二叉樹。

如下圖所示，任意一個(gè)從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑總是一個(gè)單調(diào)不降的序列。

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

4、作用

還是以大頂堆為例，堆能夠在 O ( 1 ) O(1) O(1) 的時(shí)間內(nèi)，獲得 關(guān)鍵字 最大的元素。并且能夠在 O ( l o g 2 n ) O(log_2n) O(log2?n) 的時(shí)間內(nèi)執(zhí)行插入和刪除。一般用來(lái)做 優(yōu)先隊(duì)列 的實(shí)現(xiàn)。

二、堆的存儲(chǔ)結(jié)構(gòu)

學(xué)習(xí)堆的過(guò)程中，我們能夠?qū)W到一種新的表示形式。就是：利用 數(shù)組 來(lái)表示 鏈?zhǔn)浇Y(jié)構(gòu)。怎么理解這句話呢？

由于堆本身是一棵完全二叉樹，所以我們可以把每個(gè)結(jié)點(diǎn)，按照層序映射到一個(gè)順序存儲(chǔ)的數(shù)組中，然后利用每個(gè)結(jié)點(diǎn)在數(shù)組中的下標(biāo)，來(lái)確定結(jié)點(diǎn)之間的關(guān)系。

如圖所示，描述的是堆結(jié)點(diǎn)下標(biāo)和結(jié)點(diǎn)之間的關(guān)系，結(jié)點(diǎn)上的數(shù)字代表的是 數(shù)組下標(biāo)。從左往右按照層序進(jìn)行連續(xù)遞增。

1、根結(jié)點(diǎn)編號(hào)

根結(jié)點(diǎn)的編號(hào)，看作者的喜好?？梢杂?0 或者 1。本文的作者是 C語(yǔ)言 出身，所以更傾向于選擇 0 作為根結(jié)點(diǎn)的編號(hào)（因?yàn)橛?1 作為根結(jié)點(diǎn)編號(hào)的話，數(shù)組的第 0 個(gè)元素就浪費(fèi)了）。

我們可以用一個(gè)宏定義來(lái)實(shí)現(xiàn)它的定義，如下：

#define root 0

2、孩子結(jié)點(diǎn)編號(hào)

那么，根結(jié)點(diǎn)的兩個(gè)左右子樹的編號(hào)，就分別為 1 和 2 了。以此類推，按照層序進(jìn)行編號(hào)的話，1 的左右子樹編號(hào)為 3 和 4；2 的左右子樹編號(hào)為 5 和 6。

根據(jù)數(shù)學(xué)歸納法，對(duì)于編號(hào)為 i i i 的結(jié)點(diǎn)，它的左子樹編號(hào)為 2 i + 1 2i+1 2i+1，右子樹編號(hào)為 2 i + 2 2i+2 2i+2。用宏定義實(shí)現(xiàn)如下：

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

由于這里涉及到乘 2，所以我們還可以用左移位運(yùn)算來(lái)優(yōu)化乘法運(yùn)算，如下：

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

3、父結(jié)點(diǎn)編號(hào)

同樣，父結(jié)點(diǎn)編號(hào)也可以通過(guò)數(shù)學(xué)歸納法得出，當(dāng)結(jié)點(diǎn)編號(hào)為 i i i 時(shí)，它的父結(jié)點(diǎn)編號(hào)為 i − 1 2 \frac {i-1} {2} 2i−1?，利用C語(yǔ)言實(shí)現(xiàn)如下：

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

這里涉及到除 2，可以利用右移運(yùn)算符進(jìn)行優(yōu)化，如下：

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

這里利用補(bǔ)碼的性質(zhì)，根結(jié)點(diǎn)的父結(jié)點(diǎn)得到的值為 -1；

4、數(shù)據(jù)域

堆數(shù)據(jù)元素的數(shù)據(jù)域可以定義兩個(gè)：關(guān)鍵字 和 值，其中關(guān)鍵字一般是整數(shù)，方便進(jìn)行比較確定大小關(guān)系；值則是用于展示用，可以是任意類型，可以用typedef struct進(jìn)行定義如下：

typedef struct {
    int key;      // (1)
    void *any;    // (2)
}DataType;

• (1) 關(guān)鍵字；
• (2) 值，定義成一個(gè)空指針，可以用來(lái)表示任意類型；

5、堆的數(shù)據(jù)結(jié)構(gòu)

由于堆本質(zhì)上是一棵完全二叉樹，所以將它一一映射到數(shù)組后，一定是連續(xù)的。我們可以用一個(gè)數(shù)組來(lái)代表一個(gè)堆，在C語(yǔ)言中的數(shù)組擁有一個(gè)固定長(zhǎng)度，可以用一個(gè)Heap結(jié)構(gòu)體表示如下：

typedef struct {
    DataType *data;  // (1)
    int size;        // (2)
    int capacity;    // (3)
}Heap;

• (1) 堆元素所在數(shù)組的首地址；
• (2) 堆元素個(gè)數(shù)；
• (3) 堆的最大元素個(gè)數(shù)；

三、堆的常用接口

1、元素比較

兩個(gè)堆元素的比較可以采用一個(gè)比較函數(shù)compareData來(lái)完成，比較過(guò)程就是對(duì)關(guān)鍵字key進(jìn)行比較的過(guò)程，以大頂堆為例：

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、交換元素

交換兩個(gè)元素的位置，也是堆這種數(shù)據(jù)結(jié)構(gòu)中很常見的操作，C語(yǔ)言實(shí)現(xiàn)也比較簡(jiǎn)單，如下：

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

3、空判定

空判定是一個(gè)查詢接口，即詢問(wèn)堆是否是空的，實(shí)現(xiàn)如下：

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

4、滿判定

滿判定是一個(gè)查詢接口，即詢問(wèn)堆是否是滿的，實(shí)現(xiàn)如下：

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

5、上浮操作

對(duì)于大頂堆而言，從它葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的元素關(guān)鍵字一定是單調(diào)不降的，如果某個(gè)元素出現(xiàn)了比它的父結(jié)點(diǎn)大的情況，就需要進(jìn)行上浮操作。

上浮操作就是對(duì) 當(dāng)前結(jié)點(diǎn) 和 父結(jié)點(diǎn) 進(jìn)行比較，如果它的關(guān)鍵字比父結(jié)點(diǎn)大（compareData返回-1的情況），將它和父結(jié)點(diǎn)進(jìn)行交換，繼續(xù)上浮操作；否則，終止上浮操作。

如圖所示，代表的是一個(gè)關(guān)鍵字為 95 的結(jié)點(diǎn)，通過(guò)不斷上浮，到達(dá)根結(jié)點(diǎn)的過(guò)程。上浮完畢以后，它還是一個(gè)大頂堆。

上浮過(guò)程的 C語(yǔ)言 實(shí)現(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這個(gè)接口是一個(gè)內(nèi)部接口，所以用小寫駝峰區(qū)分，用于實(shí)現(xiàn)對(duì)堆中元素進(jìn)行插入的時(shí)候的上浮操作；

(2) curr表示需要進(jìn)行上浮操作的結(jié)點(diǎn)在堆中的編號(hào)，par表示curr的父結(jié)點(diǎn)編號(hào)；

(3) 如果已經(jīng)是根結(jié)點(diǎn)，則無(wú)須進(jìn)行上浮操作；

(4) 子結(jié)點(diǎn)的關(guān)鍵字 大于 父結(jié)點(diǎn)的關(guān)鍵字，則執(zhí)行交換，并且更新新的 當(dāng)前結(jié)點(diǎn) 和 父結(jié)點(diǎn)編號(hào)；

(5) 否則，說(shuō)明已經(jīng)正確歸位，上浮操作結(jié)束，跳出循環(huán)；

6、下沉操作

對(duì)于大頂堆而言，從它 根結(jié)點(diǎn) 到 葉子結(jié)點(diǎn) 的元素關(guān)鍵字一定是單調(diào)不增的，如果某個(gè)元素出現(xiàn)了比它的某個(gè)子結(jié)點(diǎn)小的情況，就需要進(jìn)行下沉操作。

下沉操作就是對(duì) 當(dāng)前結(jié)點(diǎn) 和 關(guān)鍵字相對(duì)較小的子結(jié)點(diǎn) 進(jìn)行比較，如果它的關(guān)鍵字比子結(jié)點(diǎn)小，將它和這個(gè)子結(jié)點(diǎn)進(jìn)行交換，繼續(xù)下沉操作；否則，終止下沉操作。

如圖所示，代表的是一個(gè)關(guān)鍵字為 19 的結(jié)點(diǎn)，通過(guò)不斷下沉，到達(dá)葉子結(jié)點(diǎn)的過(guò)程。下沉完畢以后，它還是一個(gè)大頂堆。

下沉過(guò)程的 C語(yǔ)言 實(shí)現(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這個(gè)接口是一個(gè)內(nèi)部接口，所以用小寫駝峰區(qū)分，用于對(duì)堆中元素進(jìn)行刪除的時(shí)候的下沉調(diào)整；

(2) curr表示需要進(jìn)行下沉操作的結(jié)點(diǎn)在堆中的編號(hào)，son表示curr的左兒子結(jié)點(diǎn)編號(hào)；

(3) 始終選擇關(guān)鍵字更小的子結(jié)點(diǎn)；

(4) 子結(jié)點(diǎn)的值小于父結(jié)點(diǎn)，則執(zhí)行交換；

(5) 否則，說(shuō)明已經(jīng)正確歸位，下沉操作結(jié)束，跳出循環(huán)；

四、堆的創(chuàng)建

1、算法描述

通過(guò)給定的數(shù)據(jù)集合，創(chuàng)建堆。可以先創(chuàng)建堆數(shù)組的內(nèi)存空間，然后一個(gè)一個(gè)執(zhí)行堆的插入操作。插入操作的具體實(shí)現(xiàn)，會(huì)在下文繼續(xù)講解。

2、動(dòng)畫演示

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) 給定一個(gè)元素個(gè)數(shù)為dataSize的數(shù)組data，創(chuàng)建一個(gè)最大元素個(gè)數(shù)為maxSize的堆并返回堆的結(jié)構(gòu)體指針；

(2) 利用malloc申請(qǐng)堆的結(jié)構(gòu)體的內(nèi)存；

(3) 利用malloc申請(qǐng)存儲(chǔ)堆數(shù)據(jù)的數(shù)組的內(nèi)存空間；

(4) 初始化空堆；

(5) 初始化堆最大元素個(gè)數(shù)為maxSize；

(6) 遍歷數(shù)組執(zhí)行堆的插入操作，插入的具體實(shí)現(xiàn)HeapPush接下來(lái)會(huì)講到；

(7) 最后，返回堆的結(jié)構(gòu)體指針；

五、堆元素的插入

1、算法描述

堆元素的插入過(guò)程，就是先將元素插入堆數(shù)組的最后一個(gè)位置，然后執(zhí)行上浮操作；

2、動(dòng)畫演示

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) 堆已滿，不能進(jìn)行插入；

(2) 插入堆數(shù)組的最后一個(gè)位置；

(3) 對(duì)最后一個(gè)位置的 堆元素 執(zhí)行上浮操作；

五、堆元素的刪除

1、算法描述

堆元素的刪除，只能對(duì)堆頂元素進(jìn)行操作，可以將數(shù)組的最后一個(gè)元素放到堆頂，然后對(duì)堆頂元素進(jìn)行下沉操作。

2、動(dòng)畫演示

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) 堆已空，無(wú)法執(zhí)行刪除；
• (2) 將堆數(shù)組的最后一個(gè)元素放入堆頂，相當(dāng)于刪除了堆頂元素；
• (3) 對(duì)堆頂元素執(zhí)行下沉操作；

總結(jié)

本篇文章就到這里了，希望能夠給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

最新評(píng)論