#include<iostream>
#define MAX 1000
#define LEFT(i) (i<<1)//左孩子
#define RIGHT(i) (i<<1)+1//右孩子
#define PARENT(i) (i>>1)//父亲结点
#define exchage(x,y,z) {z=x;x=y;y=z;}//交换x和y

using namespace std;

int size = 0, a[MAX];

/*保证每棵子树的根节点最大*/
void MAX_HEAPIFY(int a[], int k)//维护最大堆
{
    int l = LEFT(k), r = RIGHT(k), largest, t;
    if (l <= size && a[l] > a[k])
        largest = l;
    else
        largest = k;
    if (r <= size && a[r] > a[largest])
        largest = r;
    if (largest != k)
    {
        exchage(a[largest], a[k], t);
        MAX_HEAPIFY(a, largest);
    }
}

/*从n/2到n/2+1+……+n均为子树的根节点*/
void BUILD_MAX_HEAP(int a[])//建立最大堆
{
    for (int j = PARENT(size); j > 0; j--)
        MAX_HEAPIFY(a, j);
}

void Print(int a[])
{
    for (int j = 1; j < size; j++)
        cout << a[j] << " ";
    cout << a[size] << endl;
}

void Heap_sort(int a[]);

int main()
{
    /*
    input:8
          34 56 12 545 7 3 34 23
    */
    while (1)
    {
        cout << "input the size of a[]\n";
        cin >> size;
        if (size + 1 >= MAX){ cout << "out size!\nPlease input again!\n"; }
        else break;
    }
    
    for (int j = 1; j <= size; j++)
        cin >> a[j];

    Print(a);
    BUILD_MAX_HEAP(a);
    Print(a);
    Heap_sort(a);
    cout << "堆排序后：\n";
    Print(a);
    system("pause");
    return 0;
}

/*每次都将根节点与最末尾节点交换，然后维护堆*/
void Heap_sort(int a[])//堆排序
{
    for (int j = size, t; j > 0; j--)
    {
        exchage(a[j], a[1], t);
        MAX_HEAPIFY(a, 1);
    }
}