堆排序是一種比較常用的排序方式，具有O(NlogN)的時間復雜度，它只需要一個記錄大小的空間，算法的核心是“篩選”。
堆的存儲方式是一維數組，因為它是一棵完全二叉樹，孩子與雙親下標有簡單直接的計算方式（數組下標從１開始）：節點i的左孩子下標為2 * i，右孩子下標為2 * i + 1，雙親節點下標為i / 2
堆排序的過程可分為兩步：
1.建立堆（經過n / 2次“篩選”，n為節點總個數）
2.不斷讓堆頂元素與堆的最后一個未排序的元素交換，并進行“篩選”，以維持堆的性質（該過程進行n - 1次后排序完成）。
下面我們以int型數組為例，通過建立大頂堆將數組a[]中的元素按升序排序。以下是算法代碼，其中f()是篩選函數，完成一次篩選。

 1int main()
 2{
 3    int i, j;
 4    int a[] = {0, 1, 5, 95, 7, 3, 8, 0, 90, 25, 13};
 5    int n = 10;
 6    for(i = n / 2; i > 0; i--)//從最后一個非葉子節點開始，建立大頂堆
 7    {
 8        f(a, i, n);
 9    }
10    for(i = n; i > 1; i--)//經過n - 1次交換、篩選后，完成排序。
11    {
12        swap(&a[1], &a[i]);
13        f(a, 1, i - 1);
14    }
15    //out
16    for(i = 1; i <= n; i++)
17        printf("%3d", a[i]);
18    putchar(10);
19    system("pause");
20}

以下是不同版本的篩選函數f()
void f(int *a, int top, int r)
 a為待排序數組，
 top是堆頂
 r是堆的最后一個元素
第一個是我寫的，很原始：

 1void f(int *a, int top, int r)
 2{
 3    int i = top;
 4    int lt = 2 * i;
 5    int rt = 2 * i + 1;
 6    while(lt <= r && (a[lt] > a[i] || (rt <= r && a[rt] > a[i])))
 7    {
 8        if(rt <= r)
 9        {
10            if(a[lt] > a[rt])
11            {
12                swap(&a[lt], &a[i]);
13                i = lt;
14            }
15            else
16            {
17                swap(&a[rt], &a[i]);
18                i = rt;
19            }
20        }
21        else
22        {
23            swap(&a[lt], &a[i]);
24            i = rt;
25        }
26        lt = 2 * i;
27        rt = 2 * i + 1;
28    }
29}

第二個是書上的，很簡潔：

 1void f(int *a, int top, int r)
 2{
 3    int j;
 4    for(j = 2 * top; j <= r; j *= 2)//j初始為左孩子
 5    {
 6        if(j < r && a[j] < a[j + 1]) //如果右孩子存在且比左孩子大
 7            j++;        //則讓j指向右孩子
 8        if(a[j] < a[j / 2])//如果左右孩子中較大的那個小于雙親，本次
 9            break;    //篩選結束
10        int t = a[j];
11        a[j] = a[j / 2];
12        a[j / 2] = t;
13    } 
14}

上面的算法還可以改進，以減少交換次數：

 1void f(int *a, int top, int r)
 2{
 3    int j;
 4    int  t = a[top];
 5    int top1 = top;
 6    for(j = 2 * top; j <= r; j *= 2)
 7    {
 8        if(j < r && a[j] < a[j + 1]) 
 9            j++;
10        if(a[j] < t)
11            break;
12        a[top1] = a[j];
13        top1 = j;
14    } 
15    a[top1] = t;
16}