堆是具有以下性质的完全二叉树：每个结点的值都大于等于（小于等于）其左右孩子结点的值，称为大顶堆（小顶堆）。因此，根结点一定是整个堆的最大值（最小值）。
前面讲到的简单选择排序在确定每个当前的最小值时进行了多次比较，虽然这是必须的，但是算法执行过程中并没有把比较结果保存下来，导致了无谓的一些比较。而堆这种数据结构的发明很好的解决了这个问题。根结点进行求最大值时，能够很好的利用根的子结点在求局部最大值时已经比较过的结果，进而减少了简单选择排序算法执行过程进行的重复比较的工作，使得算法的性能得以提升。直接上代码，再给大家细细讲解。如果大家忘了二叉树层序遍历时序列号的规律，还请翻看博客http://www.cnblogs.com/torresliang/p/4827109.html。
public void heapSort(int[] array) { //（1） for (int i = array.length / 2; i > 0; i--) { //（2） heapAdjust(array, i, array.length); } //（3） for (int i = array.length; i > 1; i--) { swap(array, 0, i - 1); //（4） heapAdjust(array, 1, i - 1); } //（5） } private void heapAdjust(int[] array, int s, int e) { //（6） int temp = array[s - 1]; //（7） for (int i = 2 * s; i <= e; i *= 2) { //（8） if (i < e && array[i] > array[i - 1]) //（9） i++; if (temp > array[i - 1]) //（10） break; array[s - 1] = array[i - 1]; //（11） s = i; //（12） } array[s - 1] = temp; //（13）以下是关于上述代码的讲解，由于篇幅较大，不宜放在代码中：
（1）结点序号采用层序排列，从1到n；
（2）从右到左，从下到上，分别对有子结点的父结点进行排序，联系（6）；
（3）现在，整个堆有序，根结点为最大值；
（4）每次将根结点与剩余元素中的最后一个元素交换，去掉最后一个结点（此时堆的最大值），再对剩下的堆元素进行排序·····因为堆内每次只有第一个根结点变化导致堆不再成立，故只需对根结点进行heapAdjust（）；
（5）到此为止，数组已经完全有序；
（6）调用此函数对堆进行调整时，需确保除了传进的s位置的节点外，以s结点为根的子树（即s位置结点下属的所有结点）均为有序状态，此处可以说明heapSort函数第一步为什么要从右向左，从下到上进行调整；
（7）保存s位置结点元素，否则会被覆盖。因为数组从0开始，而层序遍历序号从1开始，故均需减1；
（8）此处由上向下遍历，因为原先满足的有序状态可能因为根结点的调整而发生连锁变化，必须依次向下判断，联系（11）；
（9）首先找出左右两结点的最大值（j<e保证了有可能没有右节点的情况，此时无需比较）；
（10）判断父结点与最大子结点的大小关系，如果根原本就大，无需调整，直接结束；
（11）否则，需要调整，把最大子结点赋给父结点，这可能引起最大子结点不再大于其（最大子结点）的子结点（如果有的话），故需继续向下修复破坏的有序结构，这样就是for（）循环的意义所在。
（12）因为下次循环要检查的就是当前最大子结点以下结点的有序情况，此时的子结点就变成了下一循环的父节点；
（13）最终我们终于找到了temp（原根结点的值）应该存放的位置，赋值即可，至此，有可能已被破坏的堆调整完成，进入下次循环；
由于堆排序对原始的排序状态并不敏感，堆排序的时间复杂度为O（n*logn）。明显好于前三种排序算法。
转载于:https://www.cnblogs.com/torresliang/p/4833811.html
