堆排序的堆是怎么建立的？

堆排序，也叫二叉堆排序。
完全二叉树：
1、左右子树的节点数满足 Ln/Rn=1
2、左右子树高度满足 Rh+1>=Lh>=Rh
3、子节点值统一比父节点大（小）。

最大堆：2叉树的所有子节点都比父节点小。所以根节点是最大的。
最小堆：2叉树的所有子节点都比父节点大。所以根节点是最小的。

建堆：假设最多有N个数据。开辟一段用来存这N个数据的空间。根节点位置为0。其子节点位置为1、2。所有子节点位置与父节点的位置（k）关系：k，2k+1，2k+2。 假设已经有了n个数据，那么新数据自然放在n位（因为位置是从0开始），定义一个函数 shift_up() 用来调整新数据。它的功能是：将新数据与 (n-1)/2 位置的数据（新数据的父节点）比较，如果比父节点大，那么就交换，继续比较，直到它比父节点小。

重新建堆： 当取数据时，就是将根节点取出来。因为根节点是最大的，所以自然还要将其所有子节点进行调整，以保证剩下的数据的根节点是最大的。方法是：将最后一个数放到根节点位置（因为根节点取出后，根节点就空了），然后调用 shift_down()函数将其与1、2位置的数比较，如果比它大，则交换，然后继续与2k+1，2k+2位置的比较，直到这两个位置的数都比它小。

1,3,5,9,7,12
1 初始序列构造的堆为:
7
3 5
9 1 12
此时依据该序列进行自下而上的建堆过程：
（1） 7
1 5
9 3 12
（2） 1
3 5
9 7 12

---