完全二叉树可以和数组完美转换
若将完全二叉树的节点按构件顺序进行编号（从0开始，即树根节点编号为0）。
性质1：节点i的两个子节点的编号为2i+1和2i+2.
性质2：由性质1可得，当i > 0 时，其父节点为 floor((i-1)/2)
性质3：完全二叉树中最后一个有子节点的节点为 n/2 - 1。 n为节点数量
利用顶堆的堆积排序：
大/小顶堆的性质：
1、顶堆一定是完全二叉树，所以可以用数组直接表示
2、大/小顶堆的每个子树也是大/小顶堆
排序思路：
基本思想：把待排序的元素按照大小在二叉树位置上排列，排序好的元素要满足：父节点的元素要大于等于其子节点；这个过程叫做堆化过程，如果根节点存放的是最大的数，则叫做大根堆；如果是最小的数，自然就叫做小根堆了。根据这个特性（大根堆根最大，小根堆根最小），就可以把根节点拿出来，然后再堆化下，再把根节点拿出来，，，，循环到最后一个节点，就排序好了。
参考1：https://blog.csdn.net/YuZhiHui_No1/article/details/44258297
参考2：http://www.seotest.cn/jishu/46956.html
实现：
1、堆化过程：从最后一个分支结点（n div 2）开始，到根（1）为止，依次对每个分支结点进行调整（下沉），以便形成以每个分支结点为根的堆，当最后对树根结点进行调整后，整个树就变成了一个堆。
所谓下沉，即将节点通过不断与自己的子节点进行比较、交换，直到行进到某个位置使得自己是当前子树中最大或最小的。因为单独的下沉过程并不能保证子树的正确性。所以一定要从最下层有子节点的节点开始下沉，以保证整体算法的正确性。
2、方法是依次将堆的根节点数记下，然后删除根节点，如此反复直到堆为空。上面提到了删除操作，每次删除之后都是要调整堆让堆的性质不变，即根节点必为最大值或最小值。
具体操作可以使每次都将根节点与当前排序的数组片段的最后一位互换，然后对新数组的第一个元素进行下沉操作（并将进行堆化的数组长度-1）
由顶堆的性质（或根据堆化的过程）可知，在排序阶段，除每次的顶点外的其他顶点都是已经经过下沉操作的，所以直接对新顶点进行下沉即可得到新的顶堆
#include "core.hpp"
void heap(int *data, int size);
void ad_heap(int *data, int i, int size);
void heap(int *data, int size){
// int i, j, tmp;
// 根据性质可得，节点 i = size/2 -1 是最后一个有子节点的节点
// 且i节点之前的所有节点都一定有两个子树
// 从节点i开始向前，对所有节点进行下沉操作，保证当前节点下的所有子树的正确性
for(int i=(size/2 - 1);i>=0;i--){
ad_heap(data, i, size);
}
cout << "\n 堆积内容：";
print_array(data, size);
for(int i = size - 2; i >0; i--){
mswap(data[0], data[i+1]); // 交换堆化后数组的第一个值和最后一个值， mswap仅实现了数值交换
ad_heap(data,0, i); // 对长度减一的数组的根节点进行下沉操作
}
print_array(data, size);
}
// 该函数的作用是将节点i的值下沉到正确位置，并不是将以i为顶点的二叉树转为顶堆
// 当下沉到某个节点，使得i的值比当前节点两个子节点斗大即完成下沉
// 子树的正确性由调用函数保证
void ad_heap(int *data, int i, int size){
cout << "called====================" << endl;
int j, tmp, post;
j = 2*i + 1;
tmp = data[i];
post = 0;
while (j < size && post ==0){
cout << "j: " << j << " i: " << i << " root: " << tmp << " left: " << data[j] << endl;
if(j < size && j+1 < size){ // 标记左右子树中最大的一个
if(data[j] < data[j+1]){
j++;
}
}
if(tmp >= data[j]){ // 如果当前节点比左右子树都大则认为下沉完成
post = 1; // 不再进一步校验下一层的原因是，默认子树已经完成下沉，再进行校验就是重复校验了
}
else{
data[(j-1)/2] = data[j]; // 当前节点小于左节点或右节点，需要交换该子节点的值与当前根节点的值
j = 2*j + 1; // 因为发生了交换，不能保证交换后的各个子树仍然正确，故需要继续对下一层进行检查
}
}
data[(j-1)/2] = tmp;
print_array(data, size);
cout << "end====================" << endl;
}
int main(){
int data[8] = {34,19,40,14,57,17,4,43};
heap(data, 8);
return 0;
}
