//第一层2^0
//第二层2^1
//第三层2^2
//第k层2^(k-1)

sum=1+2^1+2^2+2^3+...+2^(k-1)=2^k-1

//总结一下：共2^k-1个节点，每层有2^(k-1)个节点

//证明也很简单：
//设父节点为F，F有两个子节点S1和S2
//节点F为第k层的第m个，所以F前肯定有m-1个节点（在第k层
//因为是完全二叉树所以S1前肯定有2(m-1)个节点所以S1是第2m-1个
//S2肯定是第2m个了

//很明显父节点坐标与子节点坐标关系：
//son_index1=2×father_index+1
//son_index2=2×father_index+2
//father_index=son_index/2(前提 father_index和on_index都是int类型

//size/2-1其实是倒数第二排的最后一个节点的下标
//假设数组的大小为size，堆的高度为k
//画图就会发现，非叶节点的个数永远是size/2（前提size是int
//所以这个循环的意思是遍历所有非叶子节点

//大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]  
//小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]  

#include <iostream>
#include <vector>

using namespace std;

void Swap(vector<int> &array, int lIndex, int rIndex);
void adjustHeap(vector<int> &array, std::size_t father, std::size_t size);
void HeapSort(vector<int> &array);
void Display(const std::vector<int> &vector);

int main()
{
    vector<int> array={9,8,7,6,5,4,3,-6};
    cout<<"before:"<<endl;
    Display(array);

    cout<<"after:"<<endl;
    HeapSort(array);
    Display(array);
}

void Swap(vector<int> &array, int lIndex, int rIndex)
{
    int temp;
    temp=array[lIndex];
    array[lIndex]=array[rIndex];
    array[rIndex]=temp;
}

//son_index1=2×father_index+1
//son_index2=2×father_index+2
void adjustHeap(vector<int> &array, std::size_t father, std::size_t size)
{
    std::size_t child;
    int temp= array[father];
    for(child= 2 * father + 1; child < size; child= 2 * child + 1)
    {
        if(child+1 < size && array[child] < array[child+1])
        {
            child++;
        }
        if(array[child] > temp)    // 如果子节点大于父节点,将子节点值赋给父节点
        {
            array[father]= array[child];
            father=child;
        } else{
            break;
        }
    }//end for
    array[father]=temp;
}

void HeapSort(vector<int> &array)
{
    int i;//i不可为size_t类型 因为当i--的时候i可能会有<0的情况 如果出现这种情况 i的值是未知的
    std::size_t size=array.size();
    // 构建大顶堆
    // 叶子节点没子节点肯定满足堆特性所以从最后一个非叶节点开始 i是下标所以-1
    for (i= (int)size/2-1;i >= 0;i--)
    {
        adjustHeap(array, i,size);
    }

    //交换堆顶元素与末尾元素+堆化
    for(i= (int)size-1;i > 0;i--)
    {
        Swap(array,0,i);    // 将堆顶元素与末尾元素进行交换
        adjustHeap(array,0,i);  // 重新对堆进行调整
    }
}

void Display(const std::vector<int> &vector)
{
    for(auto item : vector)
        printf("%d ",item);
    printf("n");
}