Heap Sort是一种基于二元树（Binary Tree）的排序演算法，具体来说就是基于完全二元树（Complete Binary Tree）来实现的，且可看成是选择排序的一种改进版本。
在Heap Sort中，先建立一个“最大堆（Max Heap）”或“最小堆（Min Heap）”，然后将堆顶元素与堆底元素互换，接着维护堆的性质，再对剩下的元素进行堆排序，重复上述步骤直到所有元素都排好序。在最大堆的情况下，堆顶元素为最大值，堆底元素为最小值；在最小堆的情况下，堆顶元素为最小值，堆底元素为最大值。
举例来说，对一个数列{3, 1, 4, 1, 5, 9, 2, 6, 5, 3}进行Heap Sort，具体步骤如下：
将数列转化成最大堆并维护其性质：
3
/ \
1 4
/ \ / \
1 5 9 2
/ \
6 5
将堆顶元素3与堆底元素3互换：
3
/ \
1 4
/ \ / \
1 5 9 2
/ \
6 5
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
3
/ \
1 4
/ \ / \
1 5 9 2
/ \
6 5
↑
3
因为堆顶元素发生了变化，所以需要重新维护堆的性质：
1
/ \
1 4
/ \ / \
3 5 9 2
/ \
6 5
重复步骤2和3，直到所有元素都排好序：
1
/ \
1 2
/ \ / \
3 5 9 4
/ \
6 5
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
1 2
/ \ / \
5 5 9 4
/ \
6 3
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
3 2
/ \ / \
5 5 9 4
/ \
6 1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
2
/ \
3 1
/ \ / \
5 5 9 4
/ \
6 1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
3 1
/ \ / \
5 5 9 4
/ \
6 2
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
3 1
/ \ / \
5 5 4 9
/ \
6 2
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
3 2
/ \ / \
5 5 4 9
/ \
6 1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
2
/ \
3 1
/ \ / \
5 5 4 9
/ \
6 1
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
3 1
/ \ / \
5 5 4 6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
3 1
/ \ / \
5 5 4 2
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
2 1
/ \ / \
5 5 4 3
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
1 2
/ \ / \
5 5 4 3
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
1 3
/ \ / \
5 5 4 2
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
2
/ \
1 3
/ \ / \
5 5 4 1
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
1 3
/ \ / \
5 5 4 2
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
1 2
/ \ / \
5 5 4 3
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
1 2
/ \ / \
5 4 5 3
\
6
\
9
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
1
/ \
1 2
/ \ / \
4 3 5 5
\
6
\
9
最终得到一个排好序的数列：{1, 1, 2, 3, 4, 5, 5, 6, 9}。
优点是平均与最坏情况下，时间复杂度均为O(nlogn)，且适用于大资料排序。但因为常数因素较大，相对于快速排序、合并排序等排序方法，速度相对较慢。
建立堆积：将待排序数列构建成堆积，需要用到“节点下标”和“节点父/子关系”两个概念，使用最大堆(或最小堆)。
对堆积进行排序：依次取出堆顶元素（最大元素），将其与堆尾元素进行交换，交换后把堆的大小减1，然后对堆顶元素从根节点做节点下潜与节点交换的操作，从而恢复最大堆（或最小堆）特性。
不断重复上述步骤，直到堆积的大小为1。
实作Heap Sort的函数，将一个阵列从小到大排序。
范例输入：[7, 5, 1, 8, 3]
范例输出：[1, 3, 5, 7, 8]
如何将Heap Sort的执行时间降至O(nlogn)?
答案：使用heapify函数来建立heap，此函数的时间复杂度为O(n)。
请解释Heap Sort不稳定的排序特性。
答案：当两个元素的值相等时，排序后它们的相对位置可能会改变。
请列出执行Heap Sort时使用的空间复杂度。
答案：Heap Sort的空间复杂度为O(1)，因为排序是直接在原始阵列上进行的。
请解释Heap Sort与Merge Sort的差异。
答案：Heap Sort使用heap来实现排序，时间复杂度为O(nlogn)，空间复杂度为O(1)。Merge Sort使用分治法来实现排序，时间复杂度为O(nlogn)，空间复杂度为O(n)。