堆排序原来如此之简单
堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。
我们知道，堆分为"最大堆"和"最小堆"。最大堆通常被用来进行"升序"排序，而最小堆通常被用来进行"降序"排序。 鉴于最大堆和最小堆是对称关系，理解其中一种即可。本文将对最大堆实现的升序排序进行详细说明。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子
该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
我们可以归纳出堆排序的基本步骤：
- 把无序数组构建成二叉堆。
- 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
特别注意：堆与数组对应关系如下图：
根据堆与数组的对应关系，堆顶元素永远位于数组第一个位置，所以循环遍历时采用从后往前循环。
具体实现看代码（代码注释已经解释很清楚）：
先构建大顶堆
public void downAdjust(int[] array, int parentIndex, int length) {
int temp = array[parentIndex];
int childIndex = parentIndex * 2 + 1;
while (childIndex < length) {
// 如果有右孩子，两孩子中找到最大值
if (childIndex + 1 < length && array[childIndex + 1] > array[childIndex]) {
childIndex++;
}
// 如果父节点大于任一子节点值，则跳出
if (temp >= array[childIndex]) {
break;
}
// 子节点上浮，更新父节点和子节点索引
array[parentIndex] = array[childIndex];
parentIndex = childIndex;
childIndex = 2 * parentIndex + 1;
}
// 完成替换
array[parentIndex] = temp;
}循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶
public void heapSort(int[] array) {
// 1、无序数组构建为大顶堆
for (int i = array.length - 1; i >= 0; i--) {
downAdjust(array, i, array.length);
}
// 堆顶元素（第一个元素），移至数组末尾，继续对前部分构建大顶堆 循环
for (int i = array.length - 1; i > 0; i--) {
int temp = array[0];
array[0] = array[i];
array[i] = temp;
downAdjust(array, 0, i);
}
}本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2019-03-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
