#include<stdio.h>
typedef int elemtype;
void Adjust(elemtype r[], int k, int n);
void HeapSort(elemtype r[], int n);

int main()
{
    int i, m;
    elemtype r[1000];
    while (1)
    {
        scanf("%d", &m);
        if (m == 0)
        {
            break;
        }
        for (i = 1; i <= m; i++)
        {
            scanf("%d", &r[i]);
        }
        HeapSort(r, m);
    }
    system("pause");
    return 0;
}
void Adjust(elemtype r[], int k, int n)//这里对数组进行升序排序 
{
    int i, j;
    elemtype tmp;
    tmp = r[k];
    i = k;
    while (i * 2 <= n)//在有孩子的情况下遍历孩子。tmp是当前结点值，它保持不变 
    {
        j = 2 * i;
        if (j + 1 <= n && r[j+1] > r[j])//找出左右孩子中的较大者childLarger 
        {
            j++;
        }
        if (tmp < r[j])
        {
            r[i] = r[j];//如果结点比childLarger小，将孩子上移到结点 
            i = j;//将下标移指向childLarger的位置 
        }
        else
        {
            break;//表明i指向的结点的孩子都比tmp小 
        }
    }
    r[i] = tmp;
}
void HeapSort(elemtype r[], int n)
{
    int i, j;
    elemtype tmp;
    for (i = n / 2; i >= 1; i--)//把树调整成大顶堆 
    {
        Adjust(r, i, n);
    }
    printf("\n\n大顶堆============================\n"); 
    for (j = 1; j <= n; j++)
    {
        printf("%d ", r[j]);
    }
    printf("===================================\n");    
    for (i = n; i >= 2; i--)
    {
        tmp = r[i];
        r[i] = r[1];
        r[1] = tmp;
        Adjust(r, 1, i - 1);//i - 1目的是不让Adjust把i上移，因为r[i]是r[1]到r[i]中的最大值 
        printf("\n-------------------------------------\n");
        for (j = 1; j <= n; j++)
        {
            printf("%d ", r[j]);
        }
    }
}

/*
11
1 3 2 5 11 7 4 13 19 6 9
*/