「堆」一詞最早源於堆排序演算法，後來才引申為「垃圾收集儲存區」的概念。在資料結構中，堆是一種陣列物件，可視為一棵完全二元樹。由於完全二元樹能以連續記憶體單元、由上而下、由左而右的方式儲存，因此堆與陣列有天然的對應關係。
圖中圓圈內的數字代表節點值，節點上方的數字則是對應的陣列索引。對於陣列 A，length[A] 表示陣列元素總數，heap-size[A] 表示堆中實際元素數，顯而易見 heap-size[A] ≤ length[A]。樹根為 A[1]，給定節點索引 i，其父節點、左子節點、右子節點索引計算公式如下：
PARENT(i) = i / 2LEFT(i) = 2iRIGHT(i) = 2i + 1二元堆分為最大堆與最小堆。最大堆滿足：除根節點外，任意節點 i 皆有 A[PARENT(i)] ≥ A[i]。換句話說，以任意節點為根的子樹中，該節點值不小於其所有子孫節點值，因此根節點必為全陣列最大值。最小堆性質恰好相反。堆排序演算法採用最大堆。
max_heapify 是保持最大堆性質的關鍵程序，時間複雜度 O(lg n)。其邏輯為：在節點 A[i] 及其左右子節點中找出最大值，若 A[i] 非最大，則與最大子節點交換，並遞迴調整受影響的子樹。
max_heapify(A, i)
l ← LEFT(i)
r ← RIGHT(i)
if l ≤ heap-size[A] and A[l] > A[i]
then largest ← l
else largest ← i
if r ≤ heap-size[A] and A[r] > A[largest]
then largest ← r
if i ≠ largest
then exchange A[i] ↔ A[largest]
max_heapify(A, largest)
上圖展示 max_heapify(A, 2) 的執行過程，讀者可對照演算法自行推演。
build_max_heap 能在線性時間內將無序陣列轉為最大堆。證明可知，含 n 元素的堆中，葉節點索引為 n/2+1, n/2+2, ..., n。因此從 length[A]/2 向前遞迴呼叫 max_heapify 即可，無需處理葉節點。
build_max_heap(A)
heap-size[A] ← length[A]
for i ← length[A]/2 downto 1
do max_heapify(A, i)
heapsort 先建立最大堆，根節點 A[1] 為最大值，將其與末尾元素 A[n] 交換，縮減堆大小，再對新根呼叫 max_heapify 恢復堆性質，重複直到堆大小為 2。整體時間複雜度 O(n lg n)，且為原地排序。
heapsort(A)
build_max_heap(A)
for i ← length[A] downto 2
do exchange A[1] ↔ A[i]
heap-size[A] ← heap-size[A] - 1
max_heapify(A, 1)
以下為以 0 為基底索引的 C 語言實作，包含交換函數、堆調整、建堆、排序主流程與測試主程式：
void swap(int *a, int *b) {
int temp = *a; *a = *b; *b = temp;
}
void max_heapify(int *arr, int i, int size) {
int lt = 2*i + 1; // 左子節點
int rt = 2*i + 2; // 右子節點
int large;
if (lt <= size-1 && arr[lt] > arr[i]) large = lt;
else large = i;
if (rt <= size-1 && arr[rt] > arr[large]) large = rt;
if (large != i) {
swap(&arr[i], &arr[large]);
max_heapify(arr, large, size);
}
}
void build_max_heap(int *arr, int size) {
for (int i = size/2; i >= 0; i--)
max_heapify(arr, i, size);
}
void heapsort(int *arr, int size) {
int len = size;
build_max_heap(arr, size);
for (int i = size; i >= 1; i--) {
swap(&arr[0], &arr[i-1]);
len--;
max_heapify(arr, 0, len);
}
}
int main(void) {
int arr[] = {4,1,3,2,16,9,10,14,8,7};
int len = sizeof(arr)/sizeof(arr[0]);
heapsort(arr, len);
for (int i = 0; i < len; i++) printf("%d ", arr[i]);
return 0;
}
執行結果將輸出排序後的陣列：1 2 3 4 7 8 9 10 14 16。
