首先说一下堆的概念，堆分小顶堆和大顶堆。
小顶堆，堆顶元素小于左子树及右子树上边的值，同时左右子树也是小顶堆，这样类推下去。同理大顶堆，就是堆顶元素大于左右子树所有元素，左右子树也分别是大顶堆。
下边开始算法解释
排序时每次将堆顶元素取走，将最后一个元素放在第一个元素的位置上，然后将剩下的i-1个元素重新调整为堆，依次类推。及排序过程就是不断的调整堆的过程。
我们讨论顺序排序，数组a[0-n-1]，i 做循环元素，从n-1开始，将0~i元素调整为大顶堆，然后将第0个元素和第i个元素交换。然后再对i-1个元素作堆调整，依次类推知道数组排序完成。
将一维数组中的树看成一个完全二叉树（完全二叉树除了叶子节点以外，所有节点都有左右两个孩子节点，具体概念可百度），即例如一组数：{49,38,65,97,76,13,27,49}
看成二叉树形式：
首先将其调整成大顶堆（由于完全二叉树的最后一个非叶子节点元素为 n/2（,完全二叉树的性质，可先行理解完全二叉树）故从下标n/2开始调整到下标0）调整过程：
1.由于49小于97，故不需要调整
2.由于65大于13和27故不需要调整
3.由于38小于97个76，且97大于76，故将97和和38交换
由于交换后38小于49，故需要交换
4.由于49小于左右子树，故将左右子树中偏大者即97与49交换
交换完之后，49小于76，故将76余49交换
至此，一个又鲜又嫩的大顶堆调整好了。
然后将97移除，即在数组中放在最后一个位置（不再参与堆调整），然后将38调整到第一位
同理进行类似的堆调整，然后将堆顶元素移除（即在数组中方在倒数第二个位置，不再参与堆调整），将最后一个元素放在第一个元素，然后进行堆调整。依次类推
直到所有的元素调整好。
代码如下
package heap;
import java.util.Arrays;
public class HeapSort {
public static void main(String[] args) {
int[] a = new int[] { 33, 9, 34, 12, 6, 10, 8, 9, 32, 1 };
int[] b = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11 };
HeapSort heapSort = new HeapSort();
heapSort.heapSort(a);
heapSort.heapSort(b);
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(b));
}
public void heapAdjust(int[] a, int s, int e) {
int rc = a[s];//记录堆顶元素的值，然后将其与左右子树的值进行比较
//将较大者网上填，最后找到适合rc的位置填入其中，由于数组下标从0开始，故其左子树为2*s+1而不是2*s
for (int i = 2 * s + 1; i <= e; i = 2 * i + 1) {
if (i < e && a[i + 1] > a[i])
i++;//找出左右孩子中较大者
if (rc > a[i])
break;//比较较大者与待调整元素的大小
a[s] = a[i];//将较大者赋值为父节点
s = i;//记录rc需要填写的位置
}
a[s] = rc;//元素归为
}
public void heapSort(int[] a) {
int length = a.length;
int tmp;
int i;
for (i = length / 2 - 1; i >= 0; i--) {
heapAdjust(a, i, length - 1);//从n/2个元素开始调整，直到第一个元素，调整为一个大顶堆
}
for (i = length - 1; i > 0; i--) {
tmp = a[i];//
a[i] = a[0];//将堆顶元素与最后一个元素交换，即移除堆顶元素，将最后一个元素放在第一个元素
a[0] = tmp;
heapAdjust(a, 0, i - 1);//调整前i-1个元素为大顶堆，i元素不再参与堆调整
}
}
}
