思想
堆排序在排序算法中属于比较难的一个了，首先阐明一些概念。
堆的实质是一颗完全二叉树，假如一颗二叉树的层数的h,那么这可二叉树的h-1层都是满二叉树。
假如堆中的父节点的值<子节点的值，这个堆叫做小根堆
假如堆中的父节点的值>子节点的值，这个堆交大根堆。
而数组与堆的对应是顺序对应，堆就是顺序存储的二叉树，如下图所示：
堆排序的主要步骤是;
将数组Array[0]…..Array[n]构造成堆。
交换array[0] 和 array[n].将array[0]….array[n-1]构造成堆。
不断循环，直到交换了array[0]和array[1].
可以归纳为两个操作;
(1)构造堆（根据数组，构造堆）
(2)每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆或小根堆。
例子
构建堆的过程：
排序的过程：
代码
package test;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
HeapSort heapSort = new HeapSort();
int[] array = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0};
heapSort.heapSort(array);
System.out.println(Arrays.toString(array));
}
// 构造初始堆
public void adjustHeap(int [] array,int parentIndex,int length){
// 孩子节点的索引
int childIndex = parentIndex * 2 + 1;
while (childIndex < length) {
// 如果有右孩子，选出孩子节点最大的
if (childIndex + 1 < length && array[childIndex] < array[childIndex + 1]) {
childIndex ++;
}
// 如果父节点大于孩子节点，直接退出，不用进行下一步
if (array[childIndex] < array[parentIndex]) {
break;
}else{
// 把孩子节点的值和父节点的值进行交换
int temp = array[parentIndex];
array[parentIndex] = array[childIndex];
array[childIndex] = temp;
parentIndex = childIndex;
childIndex = parentIndex * 2 +1;
}
}
}
public void heapSort(int [] array) {
// 构造初始堆
for(int i = array.length /2; i >= 0;i--){
adjustHeap(array, i, array.length);
}
// 循环n-1次，每次都将第一个节点和最后一个节点交换
for(int j = array.length - 1; j>0; j--){
int temp = array[0];
array[0] = array[j];
array[j] = temp;
// 调整剩下的j-1个元素的堆
adjustHeap(array, 0,j);
}
}
}
