heap sort分析和总结

?

从上图中，我们发现，如果我们从根结点开始按照从左到右一层一层的编号的话，对这些元素的访问就构成了一个序列。比如上图中的序列按照编号顺序如下：16, 14, 10, 8, 7, 9, 3, 2, 4, 1

如果我们将这种从二叉树的结点关系转换成对应的数组形式的话，则对应的数组如下图：

?

? ? ? ? 从二叉树的每个结点的编码到它的左右字结点的关系，我们发现一个有意思的地方：

左子结点的编号=父结点编号 * 2?

右子结点的编号=父结点编号 * 2 + 1

?按照数组标的编号，有类似的对应关系：

左子结点的数组索引号= 父结点索引号 * 2

右子结点的数组索引号=父结点索引号 * 2 + 1

?

? ? 这样，我们通过一定的运算对应关系将二叉树关系的元素存储到一个数组中。针对以上的父子结点关系，他们对应的求法可以用一下几个方法实现：left(), right()。在实现的时候考虑到我们的数组下标是从0开始的，对应的关系修改为：

left(n) = n * 2 + 1 ? right(n) = n * 2 + 2

对应的代码实现如下：

left:

? ? ? ? 在上图中，我们发现值为4的结点不符合要求。那么就需要进行交换调整。接着就需要在它的两个子结点中选择最大的那个，然后交换位置。它的子结点中最大的是14.交换之后的结果如下图：
?
经过交换之后，我们发现原来元素所在的位置确实符合要求了。可是4交换到新的结点之后又不符合最大堆的条件了。没办法，还需要继续选择最大子结点进行交换。这么一交换之后的结果如下：
? ? 经过这么两轮交换，我们终于可以保证以i = 2这个结点为根的树最终达到了一个符合最大堆的状态。总结前面这么一个交换调整的过程，主要如下：
1. 比较当前结点和它的子结点，如果当前结点小于它的任何一个子结点，则和最大的那个子结点交换。否则，当前过程结束。
2. 在交换到新位置的结点重复步骤1，直到叶结点。
? ? 对上面的过程进行细化之后编码，我们可以得到两个版本的方法：
递归版本：
? ? 如果我们从根结点开始，根结点元素4比它的两个子结点都大，不需要调整。而再往后面的时候它的子结点1调整之后被换成16.这样就出现了它的子结点比它还要大的情况，因此从前往后这么调整的过程不行。
? ? 经过前面的讨论，构建最大堆的过程就相当的简单了：
public static void heapSort(int[] a){if(a == null || a.length <= 1)return;buildMaxHeap(a);int length = a.length;for(int i = a.length - 1; i > 0; i--){swap(a, i, 0);length--;maxHeapify(a, 0, length);}}
? ? 仔细看前面的代码，大家可能会发现一个细小的改变。就是maxHeapify方法多了个参数。这是因为考虑到实际情况下，如果每次我们把找到的当前集合最大元素放到后面了，那么这些元素就相当于从前面的集合中排除出来，后面进行堆调整的时候就不需要再考虑。所以用一个length的长度来限制调整的范围，以免伤及无辜：）。具体的实现可以看后面附件里的详细实现代码。
总结
? ? ? ? 堆排序粗看起来有好多个步骤，又是要建堆又是要调整的显得很复杂。其实它的过程概括起来无非就是这么两个步骤，一个就是建一个堆，然后就是每次取走根结点的元素用后面的来补，补上后进行调整，然后再重复前面的步骤。
参考资料
Introduction to algorithms
一步一步写算法（之堆排序）