ACM教程 - 堆排序

定义

堆是一种叫做完全二叉树的数据结构。这里我们用到两种堆，其实也算是一种。

• 大顶堆：每个节点的值都大于或者等于它的左右子节点的值。
• 小顶堆：每个节点的值都小于或者等于它的左右子节点的值。

Ps：小顶堆有误，节点3 和 节点2 换下位置！

如上所示，就是两种堆。如果我们把这种逻辑结构映射到数组中，就是下边这样

这个数组 arr 逻辑上就是一个堆。从这里我们可以得出以下性质（重点）

1. 对于大顶堆：arr[i] >= arr[2i + 1] && arr[i] >= arr[2i + 2]
2. 对于小顶堆：arr[i] <= arr[2i + 1] && arr[i] <= arr[2i + 2]

• 稳定性：根据 相等元素 在数组中的 相对顺序 是否被改变，排序算法可分为「稳定排序」和「非稳定排序」两类。
• 就地性：根据排序过程中 是否使用额外内存（辅助数组），排序算法可分为「原地排序」和「异地排序」两类。一般地，由于不使用外部内存，原地排序相比非原地排序的执行效率更高。
• 自适应性：根据算法 时间复杂度 是否 受待排序数组的元素分布影响 ，排序算法可分为「自适应排序」和「非自适应排序」两类。「自适应排序」的时间复杂度受元素分布影响，反之不受其影响。
• 比较类：比较类排序基于元素之间的 比较算子（小于、相等、大于）来决定元素的相对顺序；相对的，非比较排序则不基于比较算子实现。

图解

以该数组为例，构建最大堆实现从小到大排序，几个要点如下

1. 一开始构建最大堆，从最后一个非叶子节点开始直到根节点进行自底向上（从下到上，从右到左）
2. 轮到自己节点时（当前作为父节点来看待），分别比较自己的左子节点和右子节点，最终判断出最大的节点，如果最大节点是自己本身，不交换；否则自己节点和最大节点进行交换
3. 如果第 2 点不存在交换（跳过第 3 点），否则继续将换下去的子节点（原本是父节点，没错吧），继续往下维护同样的比较操作，直到没有节点了为止

• 以上构建最大堆完毕，接下来开始真正的堆排序，第一次构建完，根节点一定是最大值，换到最后 1 个叶子节点，此时最后 1 个节点到了根节点，再进行维护堆，就又会产生第 2 个最大值，然后再次将该根节点交换到倒数第 2 个叶子节点，依此类推。完毕（因为篇幅有限，只罗列解释中关键几个中间过程图例）

性质

• 时间复杂度

• 最佳 O(nlogn)
• 平均 O(nlogn)
• 最差 O(nlogn)

• 空间复杂度

• 最差 O(1)

• 稳定性：不稳定
• 就地性：原地
• 自适应性：非自适应
• 比较类：比较

Java

publicclassHeapSort {
// 入口在这publicstaticvoidheapSort(int[] arr) {
if (arr==null||arr.length==0) {
return;
        }
intlen=arr.length;
// 构建大顶堆，这里其实就是把待排序序列，变成一个大顶堆结构的数组buildMaxHeap(arr, len);
// 交换堆顶和当前末尾的节点，重置大顶堆for (inti=len-1; i>0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
        }
    }
privatestaticvoidbuildMaxHeap(int[] arr, intlen) {
// 从最后一个非叶节点开始向前遍历，调整节点性质，使之成为大顶堆for (inti= (len-1) /2; i>=0; i--) {
heapify(arr, i, len);
        }
    }
privatestaticvoidheapify(int[] arr, inti, intlen) {
// 先根据堆性质，找出它左右节点的索引intleft=2*i+1;
intright=2*i+2;
// 默认当前节点（父节点）是最大值。intlargestIndex=i;
if (left<len&&arr[left] >arr[largestIndex]) {
// 如果有左节点，并且左节点的值更大，更新最大值的索引largestIndex=left;
        }
if (right<len&&arr[right] >arr[largestIndex]) {
// 如果有右节点，并且右节点的值更大，更新最大值的索引largestIndex=right;
        }
if (largestIndex!=i) {
// 如果最大值不是当前非叶子节点的值，那么就把当前节点和最大值的子节点值互换swap(arr, i, largestIndex);
// 因为互换之后，子节点的值变了，如果该子节点也有自己的子节点，仍需要再次调整。heapify(arr, largestIndex, len);
        }
    }
privatestaticvoidswap (int[] arr, inti, intj) {
inttemp=arr[i];
arr[i] =arr[j];
arr[j] =temp;
    }
}