https://blog.csdn.net/touch_2011/article/details/6767673
几个重点
- 大小顶堆虽然逻辑形式是完全二叉树，但实际是以数组的形式存储。
- 最后一个非叶子节点（最后一个有孩子的节点）的位置是 [n/2] 向下取整。
- 为什么是[n/2]向下取整呢？在这里我简单的说明一下：设n1表示完全二叉树中有一个孩子的结点，n2表示表示完全二叉树中有两个孩子的结点，d表示非叶子结点的个数，那么总的结点个数：n=n1+2*n2+1。
（1）当n为奇数时，n1=0，n2=(n-1)/2，d=n2+n1=(n-1)/2
（2）当n为偶数时，n1=1，n2=n/2-1，d=n2+n1=n/2
由此可以看出d=[n/2]向下取整.
- 完全二叉树中拥有一个孩子的非叶子节点，只能有一个。
- 从上述推导过程可以看出，[n/2]后面的都是叶子节点，前面的都是双亲节点。
- i节点的孩子在2i，2i+1的位置。可不是+1+2
- i节点的父节点在i/2，（i-1）/2的位置。
- 堆排序的过程实际上就是建堆，取顶点，筛选法重排堆的过程。
- 时间复杂度O（2nlogn）。
- 筛选法是在子树已经是堆的情况下的递归算法，自上而下。
- 建堆也是筛选法，只不过这次只有叶子节点才是堆，所以自下而上，然后再递归下来。
