深入剖析堆原理與堆排序

2022 年 9 月 27 日
筆記

堆的介紹

完全二叉樹：完全二叉樹是滿二叉樹去除最後N個節點之後得到的樹（$N \geq0, N \in N^*$）
大根堆：節點的父親節點比自身節點大，比如根節點的值為$8$，比其子節點 $7$, $6$大，其餘的類似。

小根堆：節點的父親節點比自身節點小，比如根節點的值為$1$，比其子節點$2$, $3$的值要小，其餘的也類似。

堆的實現

如何存儲一個堆

堆的存儲是使用數組實現的，下標從0開始從左至右從上到下，依次遞增，例如上述的小根堆存儲在數組中就是

[1, 2, 3, 4, 5, 6, 7]

對應的下標為 $0, 1, 2, 3, 4, 5, 6$

如何將一個數組變成一個堆

從最後一個有孩子節點（節點下標為$M$）的元素開始，先將以該元素為根節點的子樹變成一個堆，然後下標減 $1$，再將下標為$M – 1$的節點所對應的子樹變成堆，依次遞減進行，直到根節點。示例如下（以小根堆為例）：

找到第一個有孩子節點的，由上圖容易知道，第一個有孩子節點的值為$5$，其下標為$3$，它對應的子樹為：

如果需要將上面的子樹變成一顆小根堆，只需要將$5$和$1$對應節點互換位置即可（不能和$2$換，如果和$2$換 $2>1$不符合小根堆的性質），換完之後的結果為：
然後將下標減$1$，即為$2$，對應的元素為$6$，現在也需要將其對應的子樹變成一顆小根堆，即需要將$6$和$2$互換，互換之後的結果為：
繼續將下標減$1$，然後進行相同的操作，很容易知道將$7$和$1$互換位置，互換之後的結果為：

從上面的圖可以知道，當$1$和$7$互換之後，子樹$[7, 2, 5]$不是一顆小根堆了，那怎麼辦？再將子樹$[7, 2, 5]$變成小根堆即可，所以再進行一次小根堆操作即可，將$7$, $2$進行互換即可，交換之後的結果為：

在上述的樹中，交換過程已經完成了，但是如果節點的數目非常大，或者說下面的子樹可能又出現了不符合小根堆的情況怎麼辦？那就一直循環走下去，直到沒有孩子節點或者已經滿足小根堆的性質。我們將上述操作定義為下沉(down)操作

最後再對節點$8$進行相關操作，得到的結果如下：
再對子樹進行堆化$(heapify)$操作:
在進行堆化，得到最終結果

以上就是將一個完全二叉樹變成一顆小根堆的過程，大根堆的過程非常類似，即將較大的數作為父親節點即可，就不在進行陳述~~~

程式碼實現

首先我們清楚堆的存儲數據結構是數組，那麼就有對應的下標，那麼父親節點和孩子節點的位置對應關係是什麼呢？

如果父親節點的下標為$i$那麼它對應的做孩子的下標為$2*i+1$對應右孩子的下標為$2*i+2$，如果孩子節點的下標為$i$，則對應的父親節點的下標為$\lfloor \frac{i – 1}{2} \rfloor$，可以參考下圖進行計算。

根據上面的分析我們可以知道，如果想把一個數組變成一個堆，那麼需要從最後一個有孩子的節點開始進行下沉操作，直到根節點。

下沉操作的具體步驟，如果是小根堆，就將當前節點的值和左右孩子節點進行比較，如果當前節點$V$比左右孩子節點都小的話則停止，或者當前節點沒有孩子節點也停止，如果子節點的值比當前節點小，則需要選取子節點中較小的值，然後和當前節點互換，然後在置換後對$V$重新進行上述操作。如果是大根堆則選取孩子節點中較大的值。具體程式碼如下：

#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <time.h>

#define True 1
#define False 0
#define NUM 9
#define MAX_VALUE 100

void swap(int * array, int idx1, int idx2) {
    /*交換數組的兩個元素*/
    int t = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = t;
}

void down(int * array, int length, int start, int big=False) {
    /* array 是堆數組，length 為數組的長度，start 是當前需要下沉的元素的下標，big 表示是否為大根堆 */
    while(start < length) {
        int left_child = 2 * start + 1;
        int right_child = 2 * start + 2;
        int idx = left_child;
        if (left_child > length - 1)
            /* 如果做孩子對應的下標超出數組元素個數則需要跳出循環 */
            break;
        if(right_child < length) {
            if (!big) {
                if(array[right_child] < array[left_child])
                    idx = right_child;
            } else {
                if(array[right_child] > array[left_child])
                    idx = right_child;
            }
        }
        if(!big) {
            if(array[start] > array[idx]){
                swap(array, idx, start);
                start = idx;
            } else{
                break;
            }
        } else {
            if(array[start] < array[idx]){
                swap(array, idx, start);
                start = idx;
            } else{
                break;
            }
        }
    }
}

/* 定義對整個數組的堆化過程 */
void heapify(int * array, int length, int start=-2, int big=True) {
	/* start 的默認值為 -2 表示從最後一個有孩子節點的元素開始 */
    if(start == -1) 
        /* 最後一個元素的下標為0 再減1則為-1 在這裡設置遞歸出口*/
        return;
    if (start == -2) {
        start = (length - 2) / 2;
    }
    down(array, length, start, big);
    /* 當前元素進行下沉操作之後 再對他的上一個元素進行 下沉操作*/
    heapify(array, length, start - 1, big);
}

int main() {
    int data[NUM] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    heapify(data, NUM);
    for(int i=0; i < NUM; i++) {
        printf("%d ", data[i]);
    }
    return 0;
}
/* output : 8 7 6 3 4 5 2 1 0 */

堆的應用

堆排序

對於數組array = {0, 7, 3, 5, 1, 6, 2, 4, 8}對應的堆如下圖所示，如果想使用堆排序，首先需要將數組變成一個堆，使用上面的heapify函數即可。

先將數組變成大根堆，變換過程如下圖所示：

最終得到的大根堆如圖7所示。得到一個大根堆之後怎麼排序呢？我們知道對於一個大根堆來說，根節點的孩子節點都比他小，所以根節點一定是堆中值最大的元素，現在將根節點和最後一個節點互換位置，置換後的結果如下圖所示：

現在已經將數組中最大的元素放到數組的最後一個元素了，現在我們將最後一個元素從堆中剔除，對於這個操作我們只需要將堆的長度減1，對於存儲在數組中的數據不需要改動，即現在堆中的元素只有{0, 7, 6, 5, 1, 3, 2, 4}，但是實際在數組中的元素仍然為{0, 7, 6, 5, 1, 3, 2, 4, 8}。現在對元素0進行下沉操作。操作過程如下圖所示：

最終會得到結果V，因為元素8已經不在堆中了，因此不會和8置換，這樣堆中最大的元素就在數組最後一個位置，再對剩餘元素組成的堆執行上述操作，又會將其中最大的元素放在倒數第二個位置，再對根節點的元素進行下沉操作，如此進行下去就可以排好序了。進行過程如下圖所示：

最後再將最後得到的堆（只有兩個元素）互換位置即可，這樣就是得到一個有序的數組了。從上述過程我們發現，如果初始堆是大根堆我們得到的是升序數組，如果是小根堆的話得到的將是降序數組。

堆排序程式碼實現

從上述分析過程可以直到每次置換根節點和堆最後一個節點，然後將堆長度減1，然後堆根節點的元素進行下沉操作即可，如此進行下去，直到最後堆中只有一個元素，則排序完成。具體程式碼如下：

#include <cstdio>
#include <cstring>
#include <stdlib.h>

#define True 1
#define False 0
#define NUM 9

void swap(int * array, int idx1, int idx2) {
    /* 交換數組的兩個元素 */
    int t = array[idx1];
    array[idx1] = array[idx2];
    array[idx2] = t;
}

void down(int * array, int length, int start, int big=False) {
    while(start < length) {
        int left_child = 2 * start + 1;
        int right_child = 2 * start + 2;
        int idx = left_child;
        if (left_child > length - 1)
            break;
        if(right_child < length) {
            if (!big) {
                if(array[right_child] < array[left_child])
                    idx = right_child;
            } else {
                if(array[right_child] > array[left_child])
                    idx = right_child;
            }
        }
        if(!big) {
            if(array[start] > array[idx]){
                swap(array, idx, start);
                start = idx;
            } else{
                break;
            }
        } else {
            if(array[start] < array[idx]){
                swap(array, idx, start);
                start = idx;
            } else{
                break;
            }
        }
    }
}

void heapify(int * array, int length, int start=-2, int big=True) {

    if(start == -1)
        return;
    if (start == -2) {
        start = (length - 2) / 2;
    }
    down(array, length, start, big);
    heapify(array, length, start - 1, big);
}


void heap_sort(int * array, int length, bool reverse=False) {
    for(int i = length - 1; i >=0; i--) {
        swap(array, i, 0);
        down(array, i, 0, !reverse);
    }
}

int main() {
    int data[NUM] = {0, 7, 3, 5, 1, 6, 2, 4, 8};
    heapify(data, NUM);
    for(int i=0; i < NUM; i++) {
        printf("%d ", data[i]);
    }
    heap_sort(data, NUM);
    printf("\nAfter sorted !!!\n");
    for(int i=0; i < NUM; i++) {
        printf("%d ", data[i]);
    }
    return 0;
}

堆的時間複雜度

從上面堆的結構容易知道，堆是一種二叉樹結構，如果當前堆中有元素$N$個，則向堆中插入一個元素的時間複雜度為$O(log(N))$，它在下沉的時候，數據交換的次數不會大於$log(N)$。如果一個數組（堆）中有$N$個元素，那麼它需要進行$N$次，根元素和堆的最後一個元素進行交換，然後數據進行下沉，每一次下沉的數據交換次數不會$log(N)$，而且越往後交換的次數距離$log(N)$越大，即交換的次數越來越少，因此堆排序的最大時間複雜度為$O(Nlog(N))$。

優先順序隊列

隊列就是一種先進先出的數據結構，優先順序隊列就是在隊列中優先順序最高的先出。如果用一個大於0的整型數字來代表，數據的優先順序的話（即數字越小優先順序越高）我們可以用小根堆來處理數據，因為小根堆的堆頂元素一定是一個堆中最小的，那麼每次進行pop操作，即從隊列中拿出一個元素的時候就可以將堆頂的元素和最後一個元素進行交換，然後再將新的堆頂的元素進行下沉操作即可，如果有一個新的元素進行堆，那麼它可以現在放在數組最末的位置，然後進行上浮操作，其實這個操作很簡單原理和下沉操作一模一樣，連停止條件都差不多，他們正好相反，下沉的操作噹噹前節點是葉子節點或者小於子節點的元素（對於小根堆來說）停止下沉，而上浮操作是噹噹前節點是根節點或者當前節點的值大於父親節點就停下來。下面看一個具體的操作過程。

$.\images\30.png$

$.\images\31.png$

上述一個簡單的操作過程。其實很簡單，只要掌握了下沉操作這個過程就很容易理解了，以上就是關於堆的所有內容了，如果對你有所幫助，三連~~~

以上就是本篇文章的所有內容了，我是LeHung，我們下期再見！！！更多精彩內容合集可訪問項目：//github.com/Chang-LeHung/CSCore

關注公眾號：一無是處的研究僧，了解更多電腦（Java、Python、電腦系統基礎、演算法與數據結構）知識。