堆定义及特点

堆的数据结构是完全二叉树，有大顶堆和小顶堆两种。每个非叶节点值都大于/等于其子节点称为大顶堆，每个非叶节点值小于/等于其子节点称为小顶堆。
按照层序遍历形成数组后，具有如下特点
大顶堆：A[i]>=A[2i+1] && A[i]>=A[2i+2]
小顶堆：A[i]<=A[2i+1] && A[i]<=A[2i+2]

堆排基本思想

堆排实质上是一个选择排序，只是把选择极值这个过程通过大顶堆和小顶堆来实现。将待排序列构造成一个大顶堆，此使整个序列最大值为根节点，将其与序列末尾进行交换，即最大值位于序列尾部。然后将剩下的元素构成一个新的堆，不断重复此操作，就得到一个有序序列。

实现

构造最大堆

由于每个叶节点没有子节点，已经满足了最大堆的要求，因此不用考虑。对于N个元素的数组A，只需要考虑A[N/2]到A[0]这些节点的调整。
假设位置为i处的节点，其左右子树已经为最大堆。那么比较A[i]、A[2i+1]和A[2i+2]，找出最大值，与A[i]交换。

class Heap{
public:
    void makeHeap(int A[], int length)
    {
        int i;
        for(i=length/2;i>0;i--)
        {

        }
    }

int A[9] = {1,3,5,3,6,9,11,8,7};