一.堆介绍
堆，是一棵完全二叉树，根的值大于左右子树中所有结点的值，左右子树也是堆，除此之外，对其它元素之间的大小关系（如左右子树之间元素大小关系）没有要求。
这是大根堆，如果把“大于”换成“小于“，就是小根堆，这里都以大根堆为例。
由于堆是完全二叉树，所以可以用数组来模拟，在数据结构上算是比较简单。
用数组模拟二叉树（当然也包括堆）的话，如果根节点的下标为0的话，则对于每个结点i，其左孩子下标为2*i+1；其右孩子下标为2*i+2。
堆有两个基本操作：插入元素和删除元素。
插入： 将待插入元素添加到数组末尾，然后依次向上比较，如果该结点大于父亲节点，就与父节点交换，这样就构成局部大根堆，一直到该结点小于父节点位置，便完成了结点的插入操作。
删除： 要删除某元素，可以将数组的大小缩小一，然后用数组的末尾元素代替待删除元素，然后将缩小后的数组重新调整为堆，便完成了结点的删除操作。
二.堆排序的思想
将待排序区分为无序区和有序区，无序区在前，有序区在后。未排序前无序区为整个待排序区间，没有有序区。
排序的过程是，不断地将无序区构造成一个大根堆，这样无序区中的最大元素便被放置在了数组的最前面即根的位置，然后将无序区的第一个元素与最后一个元素交换，此动作将无序区的长度缩小一，将有序区的长度扩大一，即有序区前进一，无序区向前退一。然后将新的无序区（由于根节点的变化，此时很可能已经不是大根堆）重新调整为大根堆，等待下一次的交换。如此往复，不断地将无序区的最大元素添加到有序区的前面，同时缩小无序区，直到有序区占满待排序区为止。
这样，还剩下两个问题： 1.如何将一个交换后的无序区调整为大根堆； 2.如何在排序之前建立那个初始的大根堆。
而第二个问题是可以通过第一个问题的解决而解决的。这个稍后再谈，现在先看第一个问题。
三.将一个交换后的无序区调整为大根堆(自堆顶至叶子)
由于进行元素交换前，无序区是一个大根堆，即左子树和右子树都是大根堆，所以根节点变化后左右子树仍然都是大根堆，无序区里的最大元素一定在新根节点、左右子树的根节点这三个结点里。先存储新的根节点的值以待后用。如果新的根结点最大，说明已经是大根堆，调整完毕；否则比较左右子树根节点，找出较大的，它是无序区现存的最大元素，应该作为新的大根堆中的根，所以将此节点上调至根节点位置，接下来就只需要调整此结点原来所在的子树为大根堆即可（因为大根堆对左右子树之间元素的大小关系没有要求！）。
这是一个迭代的过程，当某一个需要调整的子树调整前就已经是大根堆（待调整的根节点比左右子树根节点都大）时，或者下标已经超出无序区范围时，迭代过程结束，无序区已经调整为大根堆。
这就是调整一个左右子树都为大根堆的完全二叉树为大根堆的过程。
堆排序实例
首先，建立初始的堆结构如图：
然后，交换堆顶的元素和最后一个元素，此时最后一个位置作为有序区（有序区显示为黄色），然后进行其他无序区的堆调整，重新得到大顶堆后，交换堆顶和倒数第二个元素的位置……
重复此过程：
最后，有序区扩展完成即排序完成：
四.建立初始大根堆
若数组下标范围为0~n，考虑到单独一个元素是大根堆，则从下标[n/2]开始的元素均为大根堆。于是只要从[n/2]-1开始，向前依次构造大根堆，这样就能保证，构造到某个节点时，它的左右子树都已经是大根堆（这就可以调用我们上面讨论的调整为大根堆的方法了）。一直到下标为0的结点，就完成了初始大根堆的建立。
堆排序用到的函数有两个：1个将左右子树都为大根堆的完全二叉树调整为大根堆的调整函数；1个反复调用此调整函数来进行排序的排序函数。
本质上，堆排序就是选择排序，每次选择当前无序区最大的放入有序区。
对于直接选择排序，选择的过程要进行遍历，一次选择过程的复杂度为O(n)。堆排序利用堆的性质和二叉树的结构使得每次选择的复杂度降低为O(logn)，从而有效地改进了选择排序。
参考博文
http://blog.csdn.net/super_chris/article/details/4581900/
http://www.cnblogs.com/mengdd/archive/2012/11/30/2796845.html
本文出自 “点滴积累” 博客，请务必保留此出处http://tianxingzhe.blog.51cto.com/3390077/1658827
