看懂堆排序——堆與堆排序（三）

• 看懂堆排序——堆與堆排序（三）
  • 堆排序的基本思想
  • 代碼詳解
    • 父親下標(biāo)和孩子下標(biāo)的關(guān)系
    • 打印數(shù)組的函數(shù)
    • 下濾函數(shù)
    • 構(gòu)造堆的函數(shù)
    • 刪除最大元函數(shù)
    • 排序主函數(shù)
  • 完整代碼及運行截圖
• 參考資料

有了前面兩篇文章的鋪墊，

堆與堆排序（一）

堆與堆排序（二）

我們終于可以學(xué)習(xí)“堆排序”了。

假使給定一個數(shù)組a[N]，其包含元素a[0],a[1],a[2],…,a[N-1]，現(xiàn)要將其中元素按升序排列。如果利用堆這種數(shù)據(jù)結(jié)構(gòu)，你會怎么做?

堆排序的基本思想

很自然地想到，首先把此數(shù)組構(gòu)造成一個小根堆（利用原來的數(shù)組，原地構(gòu)造），然后依次刪除最小元素，直至堆為空。為了存儲每次刪除的最小元素，我們需要一個額外的數(shù)組，待堆為空的時候，把額外數(shù)組的內(nèi)容拷貝到原來的數(shù)組。

這種方法可行嗎？當(dāng)然可行。但是需要一個額外的數(shù)組，當(dāng)數(shù)組很大時，這個空間開銷是非常可觀的。避免使用額外的數(shù)組的聰明做法是意識到這樣一個事實：在每次刪除最小元素之后，堆的規(guī)模縮小了1. 因此，位于堆中最后的那個單元可以用來存放剛剛刪去的元素。具體來說，堆排序的步驟如下：

為給定的序列創(chuàng)建一個堆（本文以最大堆為例）

交換堆的第一個元素a[0]和最后一個元素a[n-1]

堆的大小減1（--n）。如果 n==1，算法停止；否則，對a[0]進行下濾

重復(fù)2~3步

代碼詳解

父親下標(biāo)和孩子下標(biāo)的關(guān)系

因為待排序的數(shù)組一般都是從0開始，而不是從1開始，所以之前討論的父節(jié)點和孩子節(jié)點之間的關(guān)系需要修改。

之前的是：

對于數(shù)組任一位置 i 上的元素，其左兒子在位置 2i 上，右兒子在2i+1上，它的父親則在位置 ?i/2??i/2?上。

現(xiàn)在的是：

對于數(shù)組任一位置 i 上的元素，其左兒子在位置 2i+1 上，右兒子在2i+2上，它的父親則在位置 ?(i?1)/2??(i?1)/2?上。

以節(jié)點 D 為例，D 的下標(biāo)是 3.

• B是它的父節(jié)點，B的下標(biāo)是 1（= ?(3?1)/2??(3?1)/2?），如圖中黑色的線；
• H是它的左孩子，H的下標(biāo)是 7（= 2?3+12?3+1），如圖中藍色的線；
• I是它的右孩子，I的下標(biāo)是 8（= 2?3+22?3+2），如圖中紅色的線；

所以，我們的宏定義是：

#define LEFT(i) (2*i+1) #define RIGHT(i) (2*i+2) #define PARENT(i) ((i-1)/2)

打印數(shù)組的函數(shù)

void print_array_debug(int a[], int len, int pos, char token) {for(int i=0; i<len; ++i){if( i == pos ){printf("%c %d ", token, a[i]); //打印元素值和記號}else{printf("%3d ",a[i]); //正常打印}}printf("\n\n"); }

為了展示出排序的過程，我設(shè)計了這個函數(shù)。其實這個函數(shù)和普通的打印函數(shù)差不多，無非就是多了一個在某個元素前面打印一個標(biāo)記的功能。比如要在a[0]的前面打印一個'*'，那么可以這樣調(diào)用（假設(shè)數(shù)組長度是10）：

print_array_debug(a, 10, 0, '*');

如果不想用它的打印標(biāo)記功能，則可以給pos傳一個負(fù)數(shù)，給token隨便什么值都行。比如

#define DUMMY_POS -1 #define DUMMY_TOKEN '\0'

然后調(diào)用

print_array_debug(a, 10, DUMMY_POS, DUMMY_TOKEN);

下濾函數(shù)

對于給定的數(shù)列，我們首先要對其進行“堆化”，堆化的方法如下：

在初始化一棵包含 n 個節(jié)點的完全二叉樹時，按照給定的順序來放置鍵；

從最后一個父母節(jié)點開始，到根為止，檢查這些父母節(jié)點的鍵是否滿足父母優(yōu)勢。如果該節(jié)點不滿足，就把該節(jié)點的鍵 K 和它子女的最大鍵進行交換，然后再檢查在新的位置上，K 是否滿足父母優(yōu)勢。這個過程一直繼續(xù)到 K 滿足父母優(yōu)勢為止（最終它必須滿足，因為對每個葉子中的鍵來說，這條件是自動滿足的）。

如果該節(jié)點不滿足父母優(yōu)勢，就把該節(jié)點的鍵 K 和它子女的最大鍵進行交換，然后再檢查在新的位置上，K 是否滿足父母優(yōu)勢。這個過程一直繼續(xù)到 K 滿足父母優(yōu)勢為止——這種策略叫做下濾（percolate down）。

// 下濾函數(shù)（遞歸解法） // 假定以 LEFT(t) 和 RIGHT(t) 為根的子樹都已經(jīng)是大根堆 // 調(diào)整以 t 為根的子樹，使之成為大根堆。 // 節(jié)點位置為 [0], [1], [2], ..., [n-1] void percolate_down_recursive(int a[], int n, int t) { int left = LEFT(t);int right = RIGHT(t); int max = t; //假設(shè)當(dāng)前節(jié)點的鍵值最大if(left < n) // 說明t有左孩子 {max = a[left] > a[max] ? left : max;}if(right < n) // 說明t有右孩子 {max = a[right] > a[max] ? right : max;}if(max != t){ swap(a + max, a + t); // 交換t和它的某個孩子，即t被換到了max位置percolate_down_recursive(a, n, max); // 遞歸，繼續(xù)考察t} }

構(gòu)造堆的函數(shù)

// 自底向上建堆，下濾法 void build_max_heap(element_t a[], int n) { int i;// 從最后一個父母節(jié)點開始下濾，一直到根節(jié)點for(i = PARENT(n); i >= 0; --i){ percolate_down_recursive(a, n, i);} }

刪除最大元函數(shù)

//把最大元素和堆末尾的元素交換位置，堆的規(guī)模減1，再下濾根節(jié)點 void delete_max_to_end(int heap[], int heap_size) {if(heap_size == 2) // 當(dāng)剩下2個節(jié)點的時候，交換后不用下濾{swap( heap + 0, heap + 1 ); }else if(heap_size > 2){swap( heap + 0, heap + heap_size - 1 );percolate_down_recursive(heap, heap_size-1, 0);}return; }

排序主函數(shù)

void heap_sort(int a[], int length) {build_max_heap(a,length); //堆的構(gòu)造 #ifdef PRINT_PROCEDUREprintf("build the max heap:\n");print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN); #endiffor(int size=length; size>=2; --size) //當(dāng)堆的大小為1時，停止{delete_max_to_end(a,size); #ifdef PRINT_PROCEDURE print_array_debug(a, ELMT_NUM, size-1, '|'); #endif} }

完整代碼及運行截圖

#include <stdio.h>#define LEFT(i) (2*i+1) #define RIGHT(i) (2*i+2) #define PARENT(i) ((i-1)/2) #define ELMT_NUM 10 #define DUMMY_POS -1 #define DUMMY_TOKEN '\0'typedef int element_t;void print_array_debug(int a[], int len, int pos, char token) {for(int i=0; i<len; ++i){if( i == pos ){printf("%c %d ", token, a[i]); //打印元素值和記號}else{printf("%3d ",a[i]); //正常打印}}printf("\n\n"); }//交換*a和*b void swap(int* a, int* b) {int temp = *a;*a = *b;*b = temp; }// 下濾函數(shù)（遞歸解法） // 假定以 LEFT(t) 和 RIGHT(t) 為根的子樹都已經(jīng)是大根堆 // 調(diào)整以 t 為根的子樹，使之成為大根堆。 // 節(jié)點位置為 [0], [1], [2], ..., [n-1] void percolate_down_recursive(int a[], int n, int t) { int left = LEFT(t);int right = RIGHT(t); int max = t; //假設(shè)當(dāng)前節(jié)點的鍵值最大if(left < n) // 說明t有左孩子 {max = a[left] > a[max] ? left : max;}if(right < n) // 說明t有右孩子 {max = a[right] > a[max] ? right : max;}if(max != t){ swap(a + max, a + t); // 交換t和它的某個孩子，即t被換到了max位置percolate_down_recursive(a, n, max); // 遞歸，繼續(xù)考察t} }// 自底向上建堆，下濾法 void build_max_heap(element_t a[], int n) { int i;// 從最后一個父母節(jié)點開始下濾，一直到根節(jié)點for(i = PARENT(n); i >= 0; --i){ percolate_down_recursive(a, n, i);} }//把最大元素和堆末尾的元素交換位置，堆的規(guī)模減1，再下濾根節(jié)點 void delete_max_to_end(int heap[], int heap_size) {if(heap_size == 2) // 當(dāng)剩下2個節(jié)點的時候，交換后不用下濾{swap( heap + 0, heap + 1 ); }else if(heap_size > 2){swap( heap + 0, heap + heap_size - 1 );percolate_down_recursive(heap, heap_size-1, 0);}return; }void heap_sort(int a[], int length) {build_max_heap(a,length); #ifdef PRINT_PROCEDUREprintf("build the max heap:\n");print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN); #endiffor(int size=length; size>=2; --size){delete_max_to_end(a,size); #ifdef PRINT_PROCEDURE print_array_debug(a, ELMT_NUM, size-1, '|'); #endif} }int main(void) {int a[ELMT_NUM]={4,1,3,2,16,9,10,14,8,7}; //10個printf("the array to be sorted:\n "); print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN);heap_sort(a,ELMT_NUM);printf("sort finished:\n ");print_array_debug(a,ELMT_NUM, DUMMY_POS, DUMMY_TOKEN); }

假設(shè)文件名為heap_sort.c,編譯：

gcc heap_sort.c -DPRINT_PROCEDURE

運行結(jié)果如下圖：

圖中豎線右邊的是已經(jīng)有序的元素，豎線左邊是堆。

【本系列完】

參考資料

【1】《數(shù)據(jù)結(jié)構(gòu)與算法分析（原書第2版）》（機械工業(yè)出版社，2004）
【2】《算法設(shè)計與分析基礎(chǔ)（第3版）》（清華大學(xué)出版社，2015）

總結(jié)

以上是生活随笔為你收集整理的看懂堆排序——堆与堆排序（三）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。