算法：堆排序

堆排序是指利用堆这种数据结构进行的排序算法，时间复杂度为O(n * log2(n))，和快速排序差不多快。

例题

洛谷1177 排序

题目描述
将读入的 N 个数从小到大排序后输出。

输入格式
第 1 行为一个正整数 N。
第 2 行包含 N 个空格隔开的正整数 a[i]，为你需要进行排序的数，数据保证了a[i]不超过10^9。
​
输出格式
将给定的 N个数从小到大输出，数之间用空格隔开。

输入输出样例
输入

5
4 2 4 5 1

输出

1 2 4 4 5

说明提示
对于20% 的数据，有 N <= 10^3。
对于100% 的数据，有 N <=10^5 。

堆排序

首先你需要先学会堆这个数据结构，之后再来学习堆排序这个算法。

而如果说你学会了堆，那么堆排序简直太简单了，你当然可以手写一个堆的数据结构，但这里我偷了个懒，因为其实堆这个数据结构就可以看成是一个优先队列，所以直接用priority_queue来做。思路及其简单：先把数组push进去，再一边输出top一边pop就行了。

最后，算一下算法时间复杂度：我们知道每次push和pop是log2(n)级别的复杂度，又因为这里有n个数，所以总时间复杂度是O(n * log2(n))级别的了。

代码

# include <cstdio>
# include <cmath>
# include <cstring>
# include <algorithm>
# include <queue>

using namespace std;

const int N_MAX = 100000;

int n;
int a[N_MAX + 10];

void heapSort()
{
	priority_queue <int, vector <int>, greater <int> > q;
	for (int i = 1; i <= n; i++)
		q.push(a[i]);
	for (int i = 1; i <= n; i++) {
		a[i] = q.top();
		q.pop();
	}
}

int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	heapSort();
	for (int i = 1; i <= n; i++)
		printf("%d ", a[i]);
	printf("
");
	return 0;
}