一、准备知识
1.堆
堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆是线性数据结构，相当于一维数组，有唯一后继。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
2.最大堆
把根节点最大的堆叫最大堆。
二、堆排序的思想
堆排序是将一个数组通过数组下标关系虚构出一个最大堆，这样这个最大堆的根节点是最大的，然后将这个堆的最后一个节点和根节点交换，这个最大值就到了数组的最后，然后数组的长度减一，减一后的数组在调整顺序，使其再次成为一个最大堆，这是根节点就是第二大的元素，然后将重复上面的步骤，知道全部交换完毕，数组就排好了顺序。
三、排序
1.将数组构造为一个虚拟的最大堆
通过下标来构造这个最大堆。
（1）数组下标和堆元素的对应关系。
通过上面的图，我们可以分析出，一个节点，我们可以使用(n-1)/2来计算它的父节点的坐标、使用2*n+1来计算它的左节点的坐标、使用2*n+2来计算它的右节点的坐标。
（2）构造最大堆
遍历整个数组，构造一个最大堆，每次插入一个数，然后使堆重新成为一个最大堆。构造过程如下：
- 首先将1加入堆，这时堆中只有一个元素，数组现在为[1,2,3,4,5,6,7]。
- 将2加入堆中，计算2的父节点(1-1)/2=0,2的父节点是数组下标为0的元素。这时候2成为了1的左节点，根节点小于子节点，不满足最大堆的定义，所以调整这个堆，让根节点最大，所以1,2交换位置,数组现在为[2,1,3,4,5,6,7]。
- 将3加入堆中，计算3的父节点(2-1)/2=0,3的父节点是数组下标为0的元素。这时候3成为了2的右节点，发现根节点2小于3，调整堆，将根节点2和3交换位置，现在数组为[3,1,2,4,5,6,7]。
-
重复上面的步骤，将每一个元素加入这个堆，加入一个节点后，对比加入的节点和它的父节点的大小，如果新加入的节点大于它的父节点，则将两者交换，然后在比较交换后的节点和它的父节点的大小，知道使堆重新成为一个最大堆。
构造过程代码：
2. 通过堆的结构调整来排序。
通过上面的构造，我们已将一个数组通过下标关系构造成为了一个虚拟的最大堆，这时候我们知道这个最大堆的根节点(也就是数组的第一个元素)现在肯定是所有数字中最大的一个，然后根据这个已知关系调整这个堆，来达到排序的目的。
调整过程如下：
- 将数组的第一个元素和数组的最后一个元素交换位置，这样最大的那个数就到了数组的最后，然后数组长度减一，将最后一个数排除在外，剩余的数重新调整顺序，重新成为一个最大堆，这样根节点就变成了一个次大的元素。
- 然后再次将根元素和现在的最后一个元素(原数组的倒数第二个元素)交换位置，数组长度在减一，然后重新调整堆使其再次成为一个最大堆。
- 重复上面的步骤，直到所有的数字都调整完毕，这时数组就排好了顺序。
数组调整过程：
- 找出当前节点和它的左节点、右节点三者中最大的那个节点，如果最大的节点是它自己则不做任何调整，如果最大的节点是它的左节点或者右节点，则和该节点交换位置，然后将交换后的节点作为当前节点在重复判断。
- 重复上面的步骤，使其重新成为一个最大堆。
调整过程代码如下:
四、完整代码
public class HeapSort {
public void heapSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int heapSize = arr.length;
while (heapSize > 1) {
heapify(arr, --heapSize);
}
}
private void heapInsert(int[] arr,int i) {
int last = (i - 1) / 2; //计算父节点
while (arr[i] > arr[last]) { // 比较当前节点和父节点
//调整堆
swap(arr,i,last);
//继续判断他的上一层节点是否满足最大堆
i = last;
last = (i - 1) / 2;
}
}
public void heapify(int[] arr, int heapSize) {
swap(arr, 0, heapSize--);
int cur = 0;
while (2 * cur + 1 <= heapSize) {
int left = 2 * cur + 1;
int right = 2 * cur + 2;
int lastMax = heapSize >= right && arr[left] > arr[right] ?
arr[left] > arr[cur] ? left : cur
: heapSize >= right ?
arr[right] > arr[cur] ? right : cur :
arr[left] > arr[cur]
? left : cur;
if (lastMax == cur) {
break;
}
int temp = arr[cur];
arr[cur] = arr[lastMax];
arr[lastMax] = temp;
cur = lastMax;
}
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
@Test
public void test() {
int[] arr = {1,2,3,4,5,6,7};
int[] arr1 = Arrays.copyOf(arr, arr.length);
heapSort(arr);
Arrays.sort(arr1);
Assert.assertArrayEquals(arr, arr1);
}
}
五、复杂度。
时间复杂度：O(nlogn)
空间复杂度：O(1)