封装成类：
package com.roc.algorithms.sort;
/**
* 堆排序
* a[0]不用，实际元素从角标1开始
* 父节点元素大于子节点元素
* 左子节点角标为2*k
* 右子节点角标为2*k+1
* 父节点角标为k/2
*
* @author imroc
*/
public class HeapSort {
public static void sort(int[] a) {
//s[0]不用，实际元素数量和最后一个元素的角标都为N
int N = a.length - 1;
//构造堆
//如果给两个已构造好的堆添加一个共同父节点，
//将新添加的节点作一次下沉将构造一个新堆，
//由于叶子节点都可看作一个构造好的堆，所以
//可以从最后一个非叶子节点开始下沉，直至
//根节点，最后一个非叶子节点是最后一个叶子
//节点的父节点，角标为N/2
for (int k = N / 2; k >= 1; k--) {
sink(a, k, N);
}
//下沉排序
while (N > 1) {
swap(a, 1, N--); //将大的放在数组后面，升序排序
sink(a, 1, N);
}
}
//下沉（由上至下的堆有序化）
private static void sink(int[] a, int k, int N) {
while (true) {
int i = 2 * k;
if (i > N) { //保证该节点是非叶子节点
break;
}
if (i < N && a[i + 1] > a[i]) { //选择较大的子节点
i++;
}
if (a[k] >= a[i]) { //没下沉到底就构造好堆了
break;
}
swap(a, k, i);
k = i;
}
}
private static void swap(int[] a, int i, int j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
测试：
int[] a = {-1, 9, 0, 6, 5, 8, 2, 1, 7, 4, 3};
System.out.println(Arrays.toString(a));
HeapSort.sort(a);
System.out.println(Arrays.toString(a));
输出：
[-1, 9, 0, 6, 5, 8, 2, 1, 7, 4, 3]
[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
