圖解堆排序算法

0****1

演進

結點和邊，構成一個圖。

不含環的連通圖，便成了一棵樹。每個結點擁有的子結點數稱爲結點的度。

多棵樹便構成了一個森林。

結點的度最大爲 2 的樹便是二叉樹；最大度爲 N 的是 N 叉樹，或多叉樹。

除葉子結點，每個結點的度都爲 2，稱爲滿二叉樹。
除去最後一層之後的子樹爲滿二叉樹，且最後一層結點依次從左到右分佈，則稱爲完全二叉樹。

如果在完全二叉樹上再加一個限制條件：如結點都大於等於其子結點，或者小於等於其子結點，則稱爲堆。
每個結點都大於等於其子結點，稱爲大根堆。
每個結點都小於等於其子結點，稱爲小根堆。

02

堆存儲

2.1

順序存儲：數組

用數組存儲，將一個線性數組映射成一棵完全二叉樹，父結點爲 i，則左兒子爲 2i+1，右兒子爲 2i+2。

代碼如下

int heap[10];

2.2

鏈式存儲：鏈表

定義一個結點的結構體，兩個指針分別指向左兒子和右兒子。

代碼如下

struct Node {
    int value;
    Node *lson, *rson;
};
Node *heap;

以下思想都以大根堆舉例

03

堆調整

3.1

向上調整

子結點與父結點的下標關係如下：

用一個指針指向待調整的結點：

直到指向根結點或者當前結點小於等於父結點。

代碼實現

//將heap[k]向上調整
int heapUp(int *heap, int k) {
    int parent, son, x;
    x = heap[k];
    son = k;
    parent = (son - 1) / 2;
    while (son > 0) {
        //如果父結點大於等於heap[k]則退出，否則將父結點下移
        if (heap[parent] >= x)
            break;
        heap[son] = heap[parent];
        son = parent;
        parent = (son - 1) / 2;
    }
    heap[son] = x;
    return 0;
}

3.2

向下調整

父結點與子結點的下標關係如下：

用一個指針指向待調整的結點：  

直到指向葉子結點或者當前結點大於兩個子結點。

代碼實現

//將heap[k]向下調整
int heapDown(int *heap, int k, int n) {
    int parent, son, x;
    x = heap[k];
    parent = k;
    son = 2 * k + 1;    //左孩子結點
    while (son <= n) {
        //比較左右兒子，選擇較大的一個
        if (son + 1 <= n && heap[son + 1] > heap[son])
            son++;    //使son指向左右孩子中較大的結點。
        //如果兒子結點中較大的都小於等於待調整結點則退出，否則將子結點上移
        if (heap[son] <= x)
            break;
        heap[parent] = heap[son];
        parent = son;
        son = 2 * parent + 1;
    }
    heap[parent] = x;
    return 0;
}

04

增減元素

4.1

PUSH

從堆尾插入元素，再對該元素進行向上調整直到滿足堆性質。

4.2

POP

將堆頂彈出，用堆尾的元素置換，再對堆頂的元素進行向下調整。

05

構建堆

5.1

插入構建

依次向堆尾插入元素，並對該元素進行向上調整，直到滿足堆性質。

時間複雜度：
插入一個元素要調整的高度爲 logi，所以插入 n 個元素的總次數爲 log1+log2+...+logn=log(n!)。

根據斯特林公式，有如下證明，所以複雜度 O(nlogn)。

5.2

調整構建

待調整的數組，可以直接看成是一棵完全二叉樹。

從 (n-1)/2 位置開始，將每個元素進行向下調整，直到根結點。對於每一個待調整的當前結點，下面的子樹都已經滿足堆性質，所以調整完所有結點便成了堆。

時間複雜度：
倒數第二層有 2^(h-2) 個結點，調整高度爲 1，依次類推，第一層有 1 個結點，調整高度爲 h-1，整體加起來的複雜度爲 O(n)。

代碼實現

void buildHeap(int *heap, int n) {
    for (int i = (n - 1) / 2; i >= 0; --i) {
        heapDown(heap, i, n);
    }
}

06

排序

一個已經調整完成的大根堆。

核心思想：  

重複以上過程直到整體元素爲 1，這時就變成了一個升序排列的數組。  

模擬過程：

Step 1

Step 2

代碼實現

void swap(int *heap, int a, int b) {
    int temp;
    temp = heap[a];
    heap[a] = heap[b];
    heap[b] = temp;
}
void heapsort(int *heap, int n) {
    for (int i = n; i > 0; --i) {
        swap(heap, 0, i);
        heapDown(heap, 0, i - 1);
    }
}

07

總結

堆排的複雜度爲 nlogn，應用場景很廣泛，這篇文章主要講清楚堆相關的操作，具體的應用和建模以後會再專門寫文章講解。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Q9igjwG1WCwYFkeowfpqTg

猜你喜歡