在學習堆排序之前，首先需要了解堆的含義：在含有 n 個元素的序列中，如果序列中的元素滿足下面其中一種關系時，此序列可以稱之為堆。
對于堆的定義也可以使用完全二叉樹來解釋，因為在完全二叉樹中第 i 個結點的左孩子恰好是第 2i 個結點，右孩子恰好是 2i+1 個結點。如果該序列可以被稱為堆，則使用該序列構建的完全二叉樹中，每個根結點的值都必須不小于（或者不大于）左右孩子結點的值。
以無序表{49，38，65，97，76，13，27，49}來講，其對應的堆用完全二叉樹來表示為：
圖 3 無序表對應的堆
提示：堆用完全二叉樹表示時，其表示方法不唯一算法分析中實現堆排序c語言程序，但是可以確定的是樹的根結點要么是無序表中的最小值算法分析中實現堆排序c語言程序，要么是最大值。
通過將無序表轉化為堆，可以直接找到表中最大值或者最小值，然后將其提取出來，令剩余的記錄再重建一個堆，取出次大值或者次小值，如此反復執行就可以得到一個有序序列，此過程為堆排序。
堆排序過程的代碼實現需要解決兩個問題：如何將得到的無序序列轉化為一個堆？在輸出堆頂元素之后（完全二叉樹的樹根結點），如何調整剩余元素構建一個新的堆？首先先解決第 2 個問題。圖 3 所示為一個完全二叉樹，若去除堆頂元素，即刪除二叉樹的樹根結點，此時用二叉樹中最后一個結點 97 代替，如下圖所示：
此時由于結點 97 比左右孩子結點的值都大，破壞了堆的結構，所以需要進行調整：首先以 堆頂元素 97 同左右子樹比較，同值最小的結點交換位置，即 27 和 97 交換位置：
由于替代之后破壞了根結點右子樹的堆結構，所以需要進行和上述一樣的調整，即令 97 同 49 進行交換位置：
通過上述的調整，之前被破壞的堆結構又重新建立。從根結點到葉子結點的整個調整的過程，被稱為“篩選”。
解決第一個問題使用的就是不斷篩選的過程，如下圖所示，無序表{49，38，65，97，76，13，27，49}初步建立的完全二叉樹，如下圖所示：
在對上圖做篩選工作時，規律是從底層結點開始，一直篩選到根結點。對于具有 n 個結點的完全二叉樹，篩選工作開始的結點為第 ?n/2?個結點（此結點后序都是葉子結點，無需篩選）。
所以，對于有 9 個結點的完全二叉樹，篩選工作從第 4 個結點 97 開始，由于 97 > 49 ,所以需要相互交換，交換后如下圖所示：
然后再篩選第 3 個結點 65 ，由于 65 比左右孩子結點都大，則選擇一個最小的同 65 進行交換，交換后的結果為：
然后篩選第 2 個結點，由于其符合要求，所以不用篩選；最后篩選根結點 49 ，同 13 進行交換，交換后的結果為：
交換后，發現破壞了其右子樹堆的結構，所以還需要調整，最終調整后的結果為：
所以實現堆排序的完整代碼為：
#include#include #define MAX 9 //單個記錄的結構體 typedef struct { int key; }SqNote; //記錄表的結構體 typedef struct { SqNote r[MAX]; int length; }SqList; //將以 r[s]為根結點的子樹構成堆，堆中每個根結點的值都比其孩子結點的值大 void HeapAdjust(SqList * H,int s,int m){ SqNote rc=H->r[s];//先對操作位置上的結點數據進行保存，放置后序移動元素丟失。 //對于第 s 個結點，篩選一直到葉子結點結束 for (int j=2*s; j<=m; j*=2) { //找到值最大的孩子結點 if (j+1 r[j].key r[j+1].key)) { j++; } //如果當前結點比最大的孩子結點的值還大，則不需要對此結點進行篩選，直接略過 if (!(rc.key r[j].key)) { break; } //如果當前結點的值比孩子結點中最大的值小，則將最大的值移至該結點，由于 rc 記錄著該結點的值，所以該結點的值不會丟失 H->r[s]=H->r[j]; s=j;//s相當于指針的作用，指向其孩子結點，繼續進行篩選 } H->r[s]=rc;//最終需將rc的值添加到正確的位置 } //交換兩個記錄的位置 void swap(SqNote *a,SqNote *b){ int key=a->key; a->key=b->key; b->key=key; } void HeapSort(SqList *H){ //構建堆的過程 for (int i=H->length/2; i>0; i--) { //對于有孩子結點的根結點進行篩選 HeapAdjust(H, i, H->length); } //通過不斷地篩選出最大值，同時不斷地進行篩選剩余元素 for (int i=H->length; i>1; i--) { //交換過程，即為將選出的最大值進行保存大表的最后，同時用最后位置上的元素進行替換，為下一次篩選做準備 swap(&(H->r[1]), &(H->r[i])); //進行篩選次最大值的工作 HeapAdjust(H, 1, i-1); } } int main() { SqList * L=(SqList*)malloc(sizeof(SqList)); L->length=8; L->r[1].key=49; L->r[2].key=38; L->r[3].key=65; L->r[4].key=97; L->r[5].key=76; L->r[6].key=13; L->r[7].key=27; L->r[8].key=49; HeapSort(L); for (int i=1; i<=L->length; i++) { printf("%d ",L->r[i].key); } return 0; }
運行結果為：
13 27 38 49 49 65 76 97
提示:代碼中為了體現構建堆和輸出堆頂元素后重建堆的過程，堆在構建過程中，采用的是堆的第二種關系，即父親結點的值比孩子結點的值大；重建堆的過程也是如此。
堆排序在最壞的情況下，其時間復雜度仍為O(nlogn)。這是相對于快速排序的優點所在。同時堆排序相對于樹形選擇排序，其只需要一個用于記錄交換（rc）的輔助存儲空間，比樹形選擇排序的運行空間更小。