数据结构与算法-排序（六）堆排序（Heap Sort）
摘要
堆排序需要用到一种数据结构，大顶堆。大顶堆是一种二叉树结构，本质是父节点的数大于它的左右子节点的数，左右子节点的大小顺序不限制，也就是根节点是最大的值。
这里就是不断的将大顶堆的根节点的元素和尾部元素交换，交换到大顶堆没有可以被交换的元素为止。后面再说大顶堆的逻辑。
逻辑
首先将序列通过大顶堆排序。然后不断的从堆中取出顶部元素放在尾部，直到大顶堆元素为空。
流程
- 对序列进行原地建堆操作
- 重复下面操作，直到堆元素数量为 1
- 交换堆顶元素与尾元素
- 堆的元素数量减 1
- 对 0 位置进行 1 次 自下而上的下滤
下面在代码中解释原地建堆和自下而上的下滤这两个词的逻辑。
实现
首先进行原地建堆。原地建堆是先将序列按照大顶堆的排序逻辑处理序列。
大顶堆的序列逻辑是父节点的值大于它的左右子节点的值，可以想象成一个二叉树。这里的原地排序用到了siftDown方法，而且在循环中只循环到序列一半数量，为什么？这个在下面看siftDown方法时详细探究一下。
// 原地建堆
// 自下而上的下滤
heapSize = array.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
交换堆顶和尾部元素，然后将需要比较的序列元素数量减少1，并将要进行比较的序列再使用siftDown方法过滤，保持序列的大顶堆的性质。然后继续开始的交换，直到可以比较的序列数量为 1 就截止。
while (heapSize > 1) {
// 交换堆顶元素和尾部元素
swap(0, --heapSize);
// 对 0 位置进行 siftDown（恢复堆的性质）
siftDown(0);
}
大顶堆的 siftDown 方法
这里来探究一下siftDown（下滤）。
二叉树的父节点和子节点的关系符合这样的公式
- leftChilder = partner * 2 + 1
- rightChilder = parnter * 2 + 1 + 1
- half （叶子）节点的数量是总节点数量的 1/2
siftDown 方法主要是将 index 位置上的元素放在合适的位置上。那么什么位置是合适的位置呢？
依据大顶堆的父节点值大于左右子节点的值的性质来看，只要是保证 index 位置的元素大于它的左右子节点就好。
看下面代码，如果 index < half 才进行循环比较，那么就有一个问题，当 index >= half 为什么不用比较？
这就要提到很巧妙的点，首先看大顶堆的性质，左右子节点没有具体顺序的要求，其次子节点的值小于父节点。那么就可以依据二叉树的叶子节点性质，如果index的位置是在叶子节点位置，那么就本来比它的父节点要小，就不用比较（这个是建立在序列本来符合大顶堆的顺序，出现一个位置的元素有变化时进行的过滤处理）。
这也是上面的原地排序中，只从一半的位置开始，是因为从这个位置开始，肯定会给它的子节点比较，过滤出大的，并放在合适位置。
代码中有三个巧妙的点
- 循环从序列的一半位置开始比较，如果位置不在前半部分，就不进行比较，这个在上面分析过
- 在比较的时候，获取到它左右子节点中最大的节点比较。在获取右子节点的时候看右子节点是否存在
rightIndex<heapSize。因为大顶堆是符合完全二叉树的（尽量往左子树安排元素）。 - 说是二叉树，但是没有实际的节点，还是一个线性序列，通过公式来获取左右子树的位置，这个就是心中有树，没有树也是树
/*
* 让 index 位置的元素下滤
*/
private void siftDown(int index) {
E element = array[index];
int half = heapSize >> 1; // 取出非叶子节点
// 第一个叶子结点的索引 == 非叶子节点的数量
// 必须保证 index 是非叶子节点
while (index < half) {
// index 的节点有2种情况
// 1、只有左子节点
// 2、同时有左右子节点
// 默认左子节点跟它进行比较
int childIndex = (index << 1) + 1;
E child = array[childIndex];
// 右子节点
int rightIndex = childIndex + 1;
if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) {
child = array[ childIndex = rightIndex];
}
if (cmp(child, element) < 0) break;
// 将子节点存放到index位置
array[index] = child;
// 重新设置 index
index = childIndex;
}
array[index] = element;
}
时间和空间复杂度
- 最好、平均时间复杂度：O(nlogn)
- 最坏时间复杂度：O((nlogn)
- 空间复杂度：O(1)
- 属于不稳定排序
题外话
这次的排序用到了二叉树和大顶堆的一些知识，可能看下来有诸多疑问，这里就先请诸位看官有个印象，后续我会分享二叉树的知识，然后在回过头来看堆排序，会让你思路大开。