共计 3900 个字符，预计需要花费 10 分钟才能阅读完成。
PS：本文系转载文章，浏览原文可读性会更好，文章开端有原文链接
目录
1、堆排序
1、1 大顶堆
1、2 小顶堆
1、3 堆排序的速度测试
1、堆排序
1、1 大顶堆
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种抉择排序，它的最坏，最好，均匀工夫复杂度均为 O(nlogn)，它也是不稳固排序；大顶堆是具备以下性质的齐全二叉树，即每个结点的值都大于或等于其左右孩子结点的值，然而咱们没有要求该结点的左孩子的值和右孩子的值的大小有任何关系。
好，咱们举个例子阐明一下大顶堆，先画一张图，如下图 1 所示：
图片
留神：图 1 中的红色数字示意节点的值，蓝色的数字示意节点的编号。
咱们对图 1 中的堆按层进行编号，映射到数组中的排序是这样的：
arr = {9 , 7 , 8 , 3 , 4 , 5 , 6 , 1 , 2}，这时候发现图 1 中的节点编号和数组 arr 的下标是一一对应的，并且有 arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 条件是成立的；个别应用大顶堆是升序排序。
好，咱们说一下将一个无序的二叉树形成大顶堆的根本思维：
（1）将待排序序列结构成一个大顶堆。
（2）此时，整个序列的最大值就是堆顶的根节点。
（3）将其与开端元素进行替换，此时开端就为最大值。
（4）而后将残余 n - 1 个元素从新结构成一个堆，这样会失去 n 个元素的次小值；如此重复执行，便能失去一个有序序列了。
看了二叉树形成大顶堆的根本思维，有的人可能就会说，还是不了解，好，咱们当初举个例子：
（1）假如咱们有一个无序的二叉树，如图 2 所示，图 2 中的二叉树映射成数组是这样的：arr = {1 , 3 , 4 , 2 , 5}；留神：红色的数字示意的是节点的值，蓝色的数字示意节点的编号，以下图雷同。
图片
（2）咱们从第一个非叶子节点开始，从下到上，从左到右，计算公式：arr.length / 2 – 1 = 5 / 2 – 1 = 1，从 1 编号开始，也就是 3 节点，以 3 节点为父节点的二叉子树（3 节点、2 节点、5 节点）中右子节点 5 是最大的，所以 3 节点和 5 节点调换地位，失去图 3 的二叉树，图 3 中的二叉树映射成数组是这样的：arr = {1 , 5 , 4 , 2 , 3}；
图片
（3）图 2 中的二叉树，3 节点所在的一层，从左到右，左边的节点（4 节点）没有子节点，所以 4 节点不必排大顶堆；从下到上，找到图 3 中二叉树的第一个非叶子节点（是 5 节点，图 2 中的第一个非叶子节点是 3 节点）的父节点，也就是 1 节点，以 1 节点为父节点的二叉子树（1 节点、5 节点、4 节点）中右子节点 5 是最大的，所以 5 节点和 1 节点调换地位，就失去了图 4 所示的二叉树，图 4 中的二叉树映射成数组是这样的：arr = {5 , 1 , 4 , 2 , 3}；
图片
（4）这时候根节点为父节点的大顶堆曾经排好了，也就是第一层的大顶堆曾经排好；然而第二层的大顶堆还没有排好，也就是根节点的左子节点 1 的大顶堆还没有排序好，于是图 4 中的二叉树以 1 节点为父节点的子树（1 节点、2 节点、3 节点）的右子节点是最大的，所以 1 节点和 3 节点调换地位，失去图 5 的二叉树，图 5 的二叉树映射的数组是这样的：arr = {5 , 3 , 4 , 2 , 1}；
图片
到了这里，图 5 的二叉树算是排好成大顶堆了，满足条件：父节点总比子节点的值大；看图 2，这里就是先从第 3 层开始做比拟，也就是叶子节点开始做比拟，比方以 3 节点为父节点造成的子树（3 节点、2 节点、5 节点），先找到较大的值（5 节点）而后“顶”到父节点，而后比拟第 2 层的节点，把第 2 层的较大值“顶”到父节点，最初最大的值肯定 3 被“顶”到根节点，所以根节点的值是最大的；排大顶堆的规定无非就是先排好根节点的大顶堆，而后再排根节点的子节点的大顶堆，再排根节点的子节点的子节点的大顶堆 ……，以此类推，最初排好叶子节点的父节点的大顶堆，最终将这棵二叉树排成大顶堆。
好了，说了这么多，咱们这里用代码实现一把：将图 2 的二叉树排成大顶堆。
public class HeapSort {
public static void main(String[] args) {
int[] arr = { 1, 3, 4, 2, 5};
HeapSort hs = new HeapSort();
hs.sort(arr);
for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);
}}
private void sort(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, arr.length);
}}
private void adjustHeap(int[] arr,int i,int length) {
int temp = arr[i];// 取出以后元素的值，保留在长期变量
//k 是 i 节点的左子节点
for (int k = 2 * i + 1;k < length;k = k * 2 + 1) {
// 左子节点的值小于右子节点的值，指向右子节点
if (k+1<length && arr[k] < arr[k+1]) {k++;}
// 如果子节点大于父节点，那就把较大的值赋值给以后节点
if (arr[k] > temp) {arr[i] = arr[k];
i = k;
} else {break;}
}
// 以 i 为父节点的最大值，放在了最顶
arr[i] = temp;}
}
日志打印如下所示：
图片
从日志能够看出，打印进去的程序的确是和图 5 的程序是一样的。
1、2 小顶堆
小顶堆是具备以下性质的齐全二叉树，即每个结点的值都小于或等于其左右孩子结点的值，然而咱们没有要求该结点的左孩子的值和右孩子的值的大小有任何关系。
将一个无序的二叉树形成大顶堆的根本思维：
（1）将待排序序列结构成一个小顶堆。
（2）此时，整个序列的最小值就是堆顶的根节点。
（3）将其与开端元素进行替换，此时开端就为最小值。
（4）而后将残余 n - 1 个元素从新结构成一个堆，这样会失去 n 个元素的次大值；如此重复执行，便能失去一个有序序列了。
小顶堆的排序和大顶堆的排序思路是相似的，都是从下往上，从左往右，也是从 arr.length / 2 – 1 这个地位的节点开始，满足 arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2] 条件是成立的；个别应用小顶堆是降序排序。
咱们就拿图 2 的二叉树来排成小顶堆来举例说明；
（1）从 arr.length / 2 – 1 这个地位的节点开始，也就是 1 编号的地位开始，以 3 节点为父节点的子树（3 节点、2 节点、5 节点）中，3 节点大于 2 节点，所以 3 节点和 2 节点调换地位，失去图 6，图 6 映射进去的数组：arr = {1，4, 2，3，5}
图片
（2）看图 6，从左到右，2 节点（序号为 1）同一层的兄弟节点（4 节点）没有子节点，所以 4 节点不必排序小顶堆；从下到上，2 节点（序号为 1）的父节点（1 节点）造成的一棵小子树（1 节点、2 节点、4 节点）中，父节点依然是最小值，所以 1 节点、2 节点、4 节点都不必换地位，第一层的小顶堆曾经排好。
（3）而后看图 6 的第二层的小顶堆是否排好，也就是看 2 节点为父节点造成的一棵小子树（2 节点、3 节点、5 节点）中，父节点依然是最小值，所以 2 节点、3 节点、5 节点都不必换地位，第二层的小顶堆也排好了。
（4）最终图 6 就排成小顶堆，对应的数组为 arr = {1，4 , 2，3，5}。
咱们用代码实现一下，把图 2 的二叉树排序成小顶堆；
public class HeapSort {
public static void main(String[] args) {
int[] arr = { 1, 3, 4, 2, 5};
HeapSort hs = new HeapSort();
hs.sort2(arr);
for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);
}}
private void sort2(int[] arr) {
for (int i = arr.length / 2 - 1; i >= 0; i--) {adjustHeap2(arr, i, arr.length);
}}
private void adjustHeap2(int[] arr,int i,int length) {
int temp = arr[i];// 取出以后元素的值，保留在长期变量
//k 是 i 节点的左子节点
for (int k = 2 * i + 1;k < length;k = k * 2 + 1) {
// 左子节点的值大于右子节点的值，指向右子节点
if (k+1<length && arr[k] > arr[k+1]) {k++;}
// 如果子节点小于父节点，那就把较小的值赋值给以后节点
if (arr[k] < temp) {arr[i] = arr[k];
i = k;
} else {break;}
}
// 以 i 为父节点的最小值，放在了最顶
arr[i] = temp;}
}
日志打印如下所示：
图片
从日志能够看出，打印进去的程序的确是和图 6 的程序是一样的。
1、3 堆排序的速度测试
堆排序的速度是很快的，在我本人的电脑上排序 9 千万条数据就用了几十毫秒的工夫，我在小顶堆的案例上批改一下主办法的代码；
public static void main(String[] args) {
int[] arr = new int[900 * 10000];
for (int i = 0; i < arr.length; i++) {arr[i] = (int)(Math.random() * 900 * 10000);
}
HeapSort hs = new HeapSort();
long start = System.currentTimeMillis();
hs.sort2(arr);
long end = System.currentTimeMillis();
System.out.println("end - start =" + (end - start));}
日志打印如下所示：
图片
