如何"建堆"？
建堆的过程是一个"从下到上"调整堆的过程。显然，叶子结点是个堆，对记录无序系列中"最后一个"分支结点而言，满足筛选的前提，即除根结点之外，其左、右子树都是堆，由此可调用算法10.13将它调整为一个堆。类似地，"从后往前"看每个记录都满足筛选的前提，依次进行调整直至对以第1个记录为根的"二叉树"进行筛选之后，整个记录序列就是一个大顶堆了。例如右侧动画所示为对前述记录无序序列进行建堆的过程。
算法 10.14 void HeapSort ( SqList &H )
{
// 对顺序表H进行堆排序
for ( i=H.length/2; i>0; --i ) // 将 H.r[1..H.length] 建成大顶堆
HeapAdjust ( H, i, H.length );
H.r[1] ←→ H.r[H.length]; // 互换"堆顶"和"堆底"的记录
for ( i=H.length-1; i>1; --i ) {
HeapAdjust(H, 1, i);// 从根开始调整，将 H.r[1..i] 重新调整为大顶堆
H.r[1] ←→ H.r[i];
// 互换"堆顶"和当前的"堆底"，使已有序的记录沉积在底部
}//for
} // HeapSort
可以证明，堆排序的时间复杂度为O (nlogn)。和选择排序雷同，无论待排序列中的记录是正序还是逆序排列，都不会使堆排序处于"最好"或"最坏"的状态。
算法10.14中第一个 for 循环调用 n/2 次筛选算法完成了建大顶堆的操作，选出序列中最大关键字记录，算法中第二个 for 循环调用 n-2 次筛选算法依次选出序列中第2大，第3大，…，第 n-1 大关键字的记录，最后被交换到 H.r[1] 位置上的记录必为关键字最小记录。
时间复杂度的详细推导请参见教材所述。