堆排HeapSort
最后更新于：2022-04-01 09:49:20
堆排序是一种树形选择排序，是对直接选择排序的有效改进。
堆的构建--》堆排：
初始状态-<从最后一个结点开始，使该子树成堆（最小/大的数移到根节点）,不断循环>-初始堆（小/大顶）--输出堆顶元素（堆顶与堆的最后一个元素交换位置）--最后一个数移至堆顶--重新建--输出堆顶元素
以下为《数据结构（C++版）习题解答与实验指导》实例
1、算法思想
堆：具有n个元素的序列（k1,k2,...,kn),当且仅当满足
时称之为堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（最大项）。
若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：
(a)大顶堆序列：（96, 83,27,38,11,09)
(b)小顶堆序列：（12，36，24，85，47，30，53，91）
初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。
因此，实现堆排序需解决两个问题：
1. 如何将n 个待排序的数建成堆；
2. 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。
首先讨论第二个问题：输出堆顶元素后，对剩余n-1元素重新建成堆的调整过程。
调整大顶堆的方法：
1）设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
2）将根结点与左、右子树中较大元素的进行交换。
3）若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.
4）若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.
5）继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
称这个自 根结点 到 叶子结点 的调整过程为筛选。如图：
再讨论对n 个元素初始建堆的过程。
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
1）n 个结点的完全二叉树，则最后一个结点是第
个结点的子树。【向下取整】
2）筛选从第
个结点为根的子树开始，该子树成为堆。
3）之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。
如图建堆初始过程：无序序列：（49，38，65，97，76，13，27，49）
2、代码实现
~~~
package sort;
public class HeapSort {
public static void main(String[] args) {
int[] src = { 66, 89, 8, 123, 9, 44, 55, 37, 200, 127, 98 };
System.out.println("初始值：");
print(src);
HeapSort(src, src.length);
System.out.println("堆排后：");
print(src);
}
/**
* 大顶堆排序算法
*/
private static void HeapSort(int src[], int length) {// 大顶堆排序算法
// 初始化堆,从最后一个节点 i= (length-1) / 2
for (int i = (length - 1) >> 1; i >= 0; --i)
HeapAdjust(src, i, length);
for (int i = length - 1; i > 0; --i) {// 从堆尾往前调整
src[i] = src[0] + (src[0] = src[i]) * 0;// 弹出堆顶最大值，堆尾值填补
HeapAdjust(src, 0, i);// 重新调整堆
}
}
/**
* src[i+1,…. ,j]已经成堆，调整 i 的子树为堆.
*
* @param src是待调整的堆数组
* @param i是待调整的数组元素的位置
* @param j是待调整数组的长度
*/
private static void HeapAdjust(int src[], int i, int j) {// 对下标为i的节点，调整其子树为堆
int temp = src[i];
int child = 2 * i + 1; // 左孩子的位置。(child+1 为当前调整结点的右孩子的位置)
while (child < j) {// 防止第一次length为偶数12时，i=5与child=11非父子关系
if (child + 1 < j && src[child] < src[child + 1]) { // 定位较大的的孩子结点
++child;
}
if (src[i] < src[child]) { // 如果较大的子结点大于父结点
src[i] = src[child]; // 那么把较大的子结点往上移动，替换它的父结点
i = child; // 更新i，以便使新子树为堆（子树结构可能改变）
src[i] = temp; // 父结点放到比它大的孩子结点上（temp值未变）
child = 2 * i + 1;// 若child<length，则继续循环建堆
} else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
break;// 防止死循环
}
}
print(src);
}
private static void print(int a[]) {
for (int i : a) {
System.out.print(i + " ");
}
System.out.println();
}
}
~~~
3、算法分析
堆排序也是一种不稳定的排序算法。
堆排序优于简单选择排序的原因：
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序的**最坏时间复杂度为O(nlogn)**。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。
堆排序在最坏的情况下，其时间复杂度也为O(nlogn)。相对于快速排序来说，这是堆排序的最大优点。此外，堆排序仅需一个记录大小的供交换用的辅助存储空间。
建堆时对于每个非终端结点来说，其实最多进行两次比较和互换操作，比较次数不超过4n 次，因此整个构建堆的时间复杂度为O(n)。
设树深度为k
，从根到叶的筛选，元素比较次数至多2(k-1)次，交换记录至多k 次。所以，在建好堆后，排序过程中的筛选次数不超过下式：
因此堆排序最坏情况下，**时间复杂度也为：O(nlogn )**。
4、算法改进
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
源码地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/sort/HeapSort.java](https://github.com/zxiaofan/Algorithm/blob/master/src/sort/HeapSort.java)