堆排序
参考资料：
http://www.cnblogs.com/jingmoxukong/p/4303826.html
如果每个节点的关键字都不大于其孩子节点的关键字，称 小根堆；
如果每个节点的关键字都不小于其孩子节点的关键字，称大根堆；
Paste_Image.png
如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。
堆中有两个父结点，元素3和元素8。
元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2i+1];
(2) 它的右孩子结点是：R[2i+2];
(3) 它的父结点是：R[(i-1)/2]*;
(4) R[i] <= R[2i+1] 且 R[i] <= R[2i+2]。
算法思路：
按照堆的定义，将数组R[0..n]调整为堆，交换R[0]和R[n];
将R[0..n-1]调整为堆，交换R[0]和R[n-1];
如此反复交换，直到交换了R[0],R[1]为止；
算法操作
- 根据初始化数组构造初始堆（构建一个完全二叉树，并保证所有的父节点，都比其孩子节点数值大）
- 每次交换第一个和最后一个元素，并输出最后一个元素（树中的最大值），然后把剩下元素，重新调整为大根堆；
- 输出完最后一个元素后，数组就排序好了；
实现算法：
// 堆排序* 左子树索引：2n+1* 游子树索引：2n+2* 堆的存储表示是顺序的。* 当想得到一个序列中第k个最小的元素之前的部分排序序列，
// 最好采用堆排序。
public class HeapSort {
public static void main(String[] args) {
int[] a = {1, 3, 4, 5, 2, 6, 9, 7, 8, 0, -1};
System.out.print("排序前： \t\t");
Utils.printArray(a);
heapSort(a);
}
public static void heapSort(int a[]) {
//1. 首先，获取该数组的 初始化为大根堆 （父节点，比所有子节点都大）
//2. 将第一个元素与最后一个元素进行交换
//3. 去除最后一个元素，并重新调整为大根堆
//4. 重复2，3，直到最后一个元素输出
// 从最后一个父节点(length/2)，开始，循环来创建 大根树
int length = a.length;
for (int i = length / 2; i >= 0; i--) {
buildMaxHeap(a, i, length - 1);
}
// 打印一下
Utils.print("初始化堆：\t");
Utils.printArray(a);
// 进行 n-1次循环，完成排序，（将不断省略最后一个数）
for (int i = length - 1; i > 0; i--) {
// 交换第一个元素与最后一个元素
int max = a[i];
a[i] = a[0];
a[0] = max;
// 调整，获取i-1个节点的堆
buildMaxHeap(a, 0, i);
System.out.format("第%d趟：\t", length - i);
Utils.printArray(a);
}
}
/**
* 为数组a，父节点parent，创建大根堆
*
* @param a 数组
* @param parentIndex父节点索引
* @param length 堆的大小
*/
public static void buildMaxHeap(int a[], int parentIndex, int length) {
int currentParentIndex = parentIndex; // 当前父节点索引
int parentValue = a[currentParentIndex]; // 父节点值
int child = currentParentIndex * 2 + 1; // 左树索引
// 如果有子树，就不断遍历 (**这段像选择排序**)
while (child < length) {
// 如果右树值 > 左树值,child 赋值为右索引
if (child + 1 < length && a[child + 1] > a[child]) {
child++;
}
// 如果当前父节点值 >= 子树值，表示，不需要查找下去了，退出循环
if (parentValue >= a[child]) {
break;
}
// 否则，将child值赋给 currentParentIndex
a[currentParentIndex] = a[child];
// 重新赋值 currentParentIndex 与 child
currentParentIndex = child;
child = child * 2 + 1; // 下一个左树
}
// 如果currentParentIndex ，被子树索引重新赋值了,
将原始parentValue，赋值给a[currentParentIndex]
if (currentParentIndex != parentIndex) {
a[currentParentIndex] = parentValue;
}
}
}
