1. 介绍2. 算法步骤3. 完整代码4. 代码说明
4.1 建堆4.2 调整堆
1. 介绍1）什么是堆？
堆是一棵顺序存储的完全二叉树。
每个结点的关键字都 小于或等于 其所有子结点的关键字，这样的堆称为小根堆。
每个结点的关键字都 大于或等于 其所有子结点的关键字，这样的堆称为大根堆。
2）什么是堆排序？
堆排序（Heapsort）是指利用堆这种数据结构来进行排序的选择排序算法。堆积是一个近似完全二叉树的结构，并同时满足子结点的值总是小于（或者大于）它的父节点。
小根堆 在排序算法中用于 升序排列；
大根堆 在排序算法中用于 降序排序；
3）注意：
堆排序 只适用于 顺序结构。
堆排序的平均时间复杂度是 O(nlongn)，最好和最坏的时间复杂度也是 O(nlongn)。空间复杂度是 O(n)
堆排序是先建堆，依此输出堆顶元素（把堆顶元素换到数组后面）后调整堆。
2. 算法步骤以 大根堆 为例，
创建一个大根堆交换堆顶和最后一个元素，剩下的元素重新调整为 大根堆 3. 完整代码
堆排序的全部代码如下（代码使用 Java 编写）：
// 堆排序
public void heapsort(int[] list) {
build(list, list.length - 1);
// 每调整一次堆，在数组最后就会多一个已经排好序的数。堆中个数为1时，不处理
for (int i = list.length - 1; i > 0; i--) {
swap(list, 0, i); // 排好序的数组中增加一个数
adjust(list, 0, i - 1);
}
}
// 建堆，自下而上建堆。先保证下面的是堆，再把前面的数加入堆中，调整为堆。
public int[] build(int[] list, int end) {
// 从最后一个父节点开始
for (int i = (end - 1) / 2; i >= 0; i--) {
adjust(list, i, end);
}
return list;
}
// 调整堆，从上自下调整。调整堆时，除了堆顶元素，其余的都满足堆的性质，所以从上向下把较大的元素移到上面
public int[] adjust(int[] list, int start, int end) {
int maxIndex, left, right;
for (int i = start; i <= (end - 1) / 2; i++) {
maxIndex = i;
left = 2 * i + 1;
right = 2 * i + 2;
if (left <= end && list[left] > list[maxIndex]) maxIndex = left;
if (right <= end && list[right] > list[maxIndex]) maxIndex = right;
if (maxIndex != i) {
int tmp = list[i];
list[i] = list[maxIndex];
list[maxIndex] = tmp;
}
}
return list;
}
// 交换元素。
void swap(int[] list, int a, int b) {
int tmp = list[a];
list[a] = list[b];
list[b] = tmp;
}
4. 代码说明
以 无序序列 a = [1,3,4,5,2] 为例，经过堆排序得到的排好序的数组是 a = [1,2,3,4,5] （也可以降序排列）。从此可以看出，把堆排序看成一个处理过程，那堆排序的输入是一个无序数组（链表不可以），输出是一个有序数组。这里以大根堆为例
堆排序
一个无序序列 a = [1,3,4,5,2] ，看出完全二叉树的物理存储结构。先建成一个初始的大根堆，建堆完成之后，数组是一个大根堆 a = [5,3,4,1,2] 。建堆完成之后，就需要将大根堆依次调整为有序序列 a = [1,2,3,4,5] 。
4.1 建堆建堆的过程，就是从最后一个父节点开始，把每一棵树调整为堆的过程。
int[] build(int[] list, int end) {
// 从最后一个父节点开始
for (int i = (end - 1)/2; i >= 0; i--) {
adjust(list, i, end);
}
return list;
}
首先来看一下，如果将一个无序序列建成大根堆。 a = [1,3,4,5,2] 画成完全二叉树之后，最后一个父节点是 [3] 。从二叉树的最后一个父节点 [3] 开始，依次向前遍历每一个父节点，直到根节点 [1] 为止。
从最后一个父节点开始要做什么事情呢？？
以当前父节点为根节点的二叉树，也就是 [3,5,2] ，将其调整为大根堆。
最后一个父节点的下标怎么计算？？
节点下标是节点在数组中的位置，所以是从 0 到 array.length - 1 。
如果一个节点下标是 i ，那么它的左子叶节点下标是 2*i+1 ，右子叶节点下标是 2*i+2。
所以，如果数组中最后一个父节点下标为 i ，最后一个元素下标是 end ，那么，最后一个元素一定是最后一个父节点的子节点。所以，就有 2*i+1 <= end 和 2*i+2 <= end ，所以可以得到最后一个父节点的下标是 (end-1)/2 。
建堆为什么是从最后一个父节点 (array.length-1)/2 开始向前遍历，而不是从 array.length-1 开始？
因为要保证调整堆时的参数是有意义的，没有越界产生。调整堆的代码中并没有判断下标是否合法。
建堆的顺序是按层次遍历的顺序遍历的，数组按从 (array.length-1)/2 到 0 访问，是按层次遍历的方式向前遍历的。
4.2 调整堆调整堆的过程，就是把堆顶元素放在合适的位置。
// 调整堆的起始、终止位置要是有效的
int[] adjust(int[] list, int start, int end) {
int maxIndex, left, right;
for (int i = start; i <= (end - 1) / 2; i++) {
maxIndex = i;
left = 2 * i + 1;
right = 2 * i + 2;
if (left <= end && list[left] > list[maxIndex]) maxIndex = left;
if (right <= end && list[right] > list[maxIndex]) maxIndex = right;
if (maxIndex != i) {
int tmp = list[i];
list[i] = list[maxIndex];
list[maxIndex] = tmp;
}
}
return list;
}
将哪个区间内的元素调整为堆？？
[start, end] ，包含左右两个下标的元素。因为调整堆的代码中并没有判断数组下标的合法性，所以传入的参数要是合法的。
怎么调整？？
首先，调整的前提是，这个树满足堆的性质，除了堆顶元素。
1）找出左右子节点中的最大值，然后和堆顶元素比较。
如果堆顶元素较大，则不用交换。如果孩子节点较大，则将堆顶元素和较大的孩子节点交换。
2）继续调整下一个节点
调整的顺序是按层次遍历的顺序遍历的，数组按从 0 到 array.length-1 访问，是按层次遍历的方式遍历的。
