#include <stdio.h>
void SwapInArray(int arr[], int x, int y)
{
/*Function：将数组中两个元素的值进行交换*/
int tmp;
tmp = arr[x];
arr[x] = arr[y];
arr[y] = tmp;
return;
}
void Heapify(int tree[], int n, int i)
{
/*Function：使tree[]中给定的以i为父节点的单个子树成为堆*/
//[递归出口]若遍历到任何一个叶节点，结束Heapify
if (i > n/2) {
return;
}
//首先默认i节点数值最大
int max = i;
//若左儿子存在且更大，暂时标记左儿子最大（先不交换，因为可能右儿子还要更大）
if (i*2 <= n && tree[i*2] > tree[max]) {
max = i*2;
}
//若右儿子存在且还要更大，标记右儿子为该三元子树中的最大节点
if (i*2+1 <= n && tree[i*2+1] > tree[max]) {
max = i*2+1;
}
//如果i不是最大，说明需要更换
if (max != i) {
//交换i和儿子max的数值（不交换编号）
SwapInArray(tree, max, i);
Heapify(tree, n, max);
/*
为什么此处需要递归？
因为我们在BuildMaxTree()中是自底向上使用Heapify()的，
可能会出现的情况是：Build之前的乱序树中，接近顶端
有一些很小很小的数，我们在Build时遍历到此处，对接近顶端的
子树使用Heapify时，这些很小的数会下沉，成为下方子树的父节点，
而它的子节点有可能比它要大，所以我们要对这些子树继续Heapify，
让这些很小的数继续下沉，有多深沉多深，
所以Heapify()需要递归调用自己来处理脚下的所有树，
保证让上面任何应该下沉的小数都下沉到它应该去的深度。
*/
}
return;
}
void BuildMaxHeap(int tree[], int n)
{
/*Function：将无序数组建立成最大堆*/
//从倒数第二层最后一个节点开始，向上遍历每一个节点，对每一个节点Heapify()
for (int i = n/2; i >= 1; i--) {
Heapify(tree, n, i);
}
}
int DeleteMax(int tree[], int n)
{
/*
将末尾叶节点值直接赋给树顶节点，
此时除了树顶外所有子树都满足最大堆，
再对树顶节点Heapify()
*/
int tmp;
tmp = tree[1];
tree[1] = tree[n];
Heapify(tree, n, 1);
return tmp;
}
int main()
{
int tree[10001];
int arr[10001];//存放排序结果
int num;
scanf("%d", &num);
for (int i = 1; i <= num; i++) {
scanf("%d", &tree[i]);
}
BuildMaxHeap(tree, num);
//倒序记录最大堆输出结果
for(int i = num; i >= 1; i--) {
arr[i] = DeleteMax(tree,i);
/*
如果每次for循环都向DeleteMax()传递参数num，
那么DeleteMax()中的n--就不起作用，
于是改成每次for循环向DeleteMax()传输i,
等效于手动删除堆的末尾叶节点.
*/
}
for (int i = 1; i <= num; i++) {
printf("%d ",arr[i]);
}
return 0;
}
