#include <iostream>
using namespace std;
void print(int *arr,int n)
{
    for(int i=0;i<10;i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}
//shiftDown对于从索引k开始检查以k为根的子树是否满足堆的定义（父节点大于孩子节点）
void shiftDown(int *arr,int n,int k)
{
    while(2*k+1<n)//2*k+1<n表示以k索引为根的子树拥有孩子
    {
        int j=2*k+1;//j索引记录要和k交换的孩子，初始化为左孩子
        if(j+1<n && arr[j+1]>arr[j])//如果右孩子比左孩子大，则j+1
        {
            j+=1;
        }
        if(arr[k]>arr[j])//如果arr[k]>arr[j]表明父节点大于最大的孩子节点，无需交换
            break;
        swap(arr[k],arr[j]);//否则交换
        k=j;
    }
}
//heapify过程建堆，让一个数组成为堆的排列
//只需要从第一个非叶子节点开始到根节点逐一shiftDown过程就好了
void heapify(int *arr,int n)
{
    for(int i=(n-1)/2;i>=0;i--)
    {
        shiftDown(arr,n,i);
    }
}
//原地堆排序，不需要开辟新的空间，由于heapify过程后数组已经成为一个堆得排列，此时arr[0]是堆顶最大元素，只需要交换arr[0]和最后一个元素，此时最后一个元素就成为最大元素，这个操作会破坏堆的排列，此时对除过最后一个元素剩下的元素进行shiftDown操作就好了
void heapSort(int *arr,int n)
{
    for(int i=n-1;i>0;i--)
    {
        swap(arr[0],arr[i]);
        shiftDown(arr, i, 0);
    }
}
int main()
{
    int arr[] {9,6,4,2,12,7,3,1,5,8};
    heapify(arr, 10);
    //print(arr,10);
    heapSort(arr, 10);
    print(arr,10);
    return 0;
}