#include<stdio.h>
#include<malloc.h>
#include<time.h>

#define MAX 10

void swap(int a[],int pos1, int pos2)
{
    int temp = a[pos1];
    a[pos1] = a[pos2];
    a[pos2] = temp;
}

void Heap_Adjust(int a[], int pos, int len)
{
    int max = pos;
    int lchild = 2*pos + 1;
    int rchild = 2*pos + 2;
    if (lchild < len && a[lchild] > a[max])
    {
        max = lchild;
    }
    if (rchild < len && a[rchild] > a[max])
    {
        max = rchild;
    }
    if (max != pos)
    {
        swap(a, max, pos);
        Heap_Adjust(a, max, len);
    }
}

void Heap_Sort(int a[], int length)
{
    // 初始化堆
    for (int i = length/2-1; i >= 0; i--)
    {
        Heap_Adjust(a, i, length);
    }
    // 交换堆顶与堆尾
    for (int i = length-1; i >= 0; i--)
    {
        swap(a, 0, i);
        Heap_Adjust(a, 0, i);
    }
    
}

void Show(int a[])
{
     for (int  i = 0; i < MAX; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
}

int main(int argc, char const *argv[])
{
    // int a[] = {4,2,5,0,5,7,1,3,9};
    int a[MAX];
    srand((unsigned int)time(NULL));
    for (int i = 0; i < MAX; i++)
    {
        a[i] = rand() % MAX;
    }
    Show(a);
    Heap_Sort(a, MAX);
    Show(a);

    return 0;
}