T625390 堆排序

堆一般指的是二叉堆，顾名思义，二叉堆是完全二叉树。 ### 1. 堆的性质 ① 是一棵完全二叉树，所以用数组法储存二叉树。 ② 每个节点的值都大于或等于其子节点的值，为最大堆；反之为最小堆。 ### 2. 堆排序 堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。 利用大顶堆（小顶堆）堆顶记录的是最大关键字（最小关键字）这一特性，使得每次从无序中选择最大记录（最小记录）变得简单。 ① 将待排序的序列构造成一个最大堆，此时序列的最大值为根节点。 ② 依次将根节点与待排序序列的最后一个元素交换。 ③ 再维护从根节点到该元素的前一个节点为最大堆，如此往复，最终得到一个递增序列。 ### 3. 实现逻辑 ① 先将初始的 $a[1\ldots n]$ 建立成最大堆，此时是无序堆，而堆顶是最大元素。 ② 再将堆顶 $a[1]$ 和无序区的最后一个记录 $a[n]$ 交换，由此得到新的无序区 $a[1\ldots n-1]$ 和有序区 $a[n]$，且满足： $$ a[1\ldots n-1] \;\le\; a[n]. $$ ③ 由于交换后新的根 $a[1]$ 可能违反堆性质，故应将当前无序区 $R[1\ldots n-1]$ 调整为堆。然后再次将该区间中关键字最大的记录 $R[1]$ 和该区间的最后一个记录 $R[n-1]$ 交换，由此得到新的无序区 $R[1\ldots n-2]$ 和有序区 $R[n-1\ldots n]$，且仍满足 $$ R[1\ldots n-2] \;\le\; R[n-1\ldots ], $$ 同样要将 $R[1\ldots n-2]$ 调整为堆。 ④ 直到无序区只有一个元素为止。 

将读入的 $N$ 个数从小到大排序后输出。

第一行为一个正整数 $N$。 第二行包含 $N$ 个空格隔开的正整数 $a_i$，为你需要进行排序的数。

将给定的 $N$ 个数从小到大输出，数之间空格隔开，行末换行且无空格。

对于 $20\%$ 的数据，有 $1 \leq N \leq 10^3$； 对于 $100\%$ 的数据，有 $1 \leq N \leq 10^5$，$1 \le a_i \le 10^9$。