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));}
日志打印如下所示：
图片