堆排序算法

输入一个长度为?n?的整数数列，从小到大输出前?m?小的数。

输入格式

第一行包含整数?n?和?m。

第二行包含?n?个整数，表示整数数列。

输出格式

共一行，包含?m?个整数，表示整数数列中前?m?小的数。

数据范围

1≤m≤n≤1e5
1≤数列中元素≤1e9

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

试题解析

1. 将待排序序列构造成一个小顶堆。
2. 此时，整个序列的最小值就是堆顶的根节点。
3. 将其与末尾元素进行交换， 此时末尾就为最小值。
4. 然后将剩余 n-1 个元素重新构造成一个堆， 这样会得到 n 个元素的次小值。 如此反复执行， 便能得到一个有序序列了。
5. 可以看到在构建小顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了。

解析代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
//用数组顺序存储完全二叉树，mySize为元素个数
int h[N], mySize;


void down(int u) {
    //记录最小点的编号
	int t = u;
	//有左儿子，且左儿子的值比t节点的值小，则更新t
	if (2 * u <= mySize && h[t] > h[2 * u]) t = 2 * u;
    //有右儿子，且右儿子的值比t节点的值小，则更新t	
	if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1]) t = 2 * u + 1;
	//如果待调整点不是最小的
	if (u != t) {
	    //和最小的交换
		swap(h[u], h[t]);
		//处理下一个
		down(t);
	}
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	mySize = n;
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &h[i]);
	}
	//从第一个非叶子节点，从右到左，从下向上处理每个节点
	for (int i = n / 2; i >= 1; i-- ) {
		down(i);
	}
	while (m --) {
	    //栈顶为最小值，输出栈顶
		cout << h[1] << " ";
		//将栈顶元素赋值为边界元素，并删除边界元素
		h[1] = h[mySize--];
		//重新处理栈顶
		down(1);
	}
	return 0;
}

?不带注释的代码

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int h[N], mySize;

void down(int u) {
	int t = u;
	if (2 * u <= mySize && h[t] > h[2 * u]) t = 2 * u;
	if (2 * u + 1 <= mySize && h[t] > h[2 * u + 1]) t = 2 * u + 1;
	if (u != t) {
		swap(h[u], h[t]);
		down(t);
	}
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	mySize = n;
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &h[i]);
	}
	for (int i = n / 2; i >= 1; i-- ) {
		down(i);
	}
	while (m --) {
		cout << h[1] << " ";
		h[1] = h[mySize--];
		down(1);
	}
	return 0;
}