在學習堆排序之前，首先需要了解堆的含義：在含有 n 個元素的序列中，如果序列中的元素滿足下面其中一種關係時，此序列可以稱之為堆。
對於堆的定義也可以使用完全二叉樹來解釋，因為在完全二叉樹中第 i 個結點的左孩子恰好是第 2i 個結點，右孩子恰好是 2i+1 個結點。如果該序列可以被稱為堆，則使用該序列構建的完全二叉樹中，每個根結點的值都必須不小於（或者不大於）左右孩子結點的值。
以無序表{49，38，65，97，76，13，27，49}來講，其對應的堆用完全二叉樹來表示為：
圖 3 無序表對應的堆
提示：堆用完全二叉樹表示時，其表示方法不唯一，但是可以確定的是樹的根結點要麼是無序表中的最小值，要麼是最大值。
通過將無序錶轉化為堆，可以直接找到表中最大值或者最小值，然後將其提取出來，令剩餘的記錄再重建一個堆，取出次大值或者次小值，如此反覆執行就可以得到一個有序序列，此過程為堆排序。
堆排序過程的代碼實現需要解決兩個問題：
如何將得到的無序序列轉化為一個堆？
在輸出堆頂元素之後（完全二叉樹的樹根結點），如何調整剩餘元素構建一個新的堆？
首先先解決第 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 <stdio.h>#include <stdlib.h>#define MAX 9typedef struct { int key;}SqNote;typedef struct { SqNote r[MAX]; int length;}SqList;void HeapAdjust(SqList * H,int s,int m){ SqNote rc=H->r[s]; for (int j=2*s; j<=m; j*=2) { if (j+1<m && (H->r[j].key<H->r[j+1].key)) { j++; } if (!(rc.key<H->r[j].key)) { break; } H->r[s]=H->r[j]; s=j; } H->r[s]=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）的輔助存儲空間，比樹形選擇排序的運行空間更小。