C/C++
满足第一种情况的堆称为小根堆（小顶堆），满足第二种情况的堆称为大根堆（大顶堆）。在大根堆中，最大元素存放在根结点中，且对任一非根结点，它的值小于或等于其双亲结点值。小根堆则恰恰相反，小根堆的根结点存放的是最小元素。例如{16, 14, 10, 8, 7, 9, 3, 2}表示的大根堆：
将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
构造初始堆成功以后，堆排序的思路就很简单了：首先将存放在L[n]中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大根堆的性质，堆被破坏。这时将堆顶元素向下调整使其继续保持大根堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩下一个元素为止。算法实现如下：构造初始堆成功以后，堆排序的思路就很简单了：首先将存放在L[n]中的n个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已不满足大根堆的性质，堆被破坏。这时将堆顶元素向下调整使其继续保持大根堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩下一个元素为止。算法实现如下：
时间复杂度：向下调整的时间与树高有关，为O(h)。可以证明在元素个数为n的序列上建堆，其时间复杂度为O(n)。之后还有n-1次向下调整操作，每次调整的时间为O(h)，故在最好，最坏和平均情况下，堆排序的时间复杂度为O(nlogn)。
空间复杂度：仅使用了常数个辅助单元，空间复杂度为O(1)。
只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止