堆排序
输入一个长度为n的整数数列,从小到大输出前m小的数。
输入格式
第一行包含整数n和m。
第二行包含n个整数,表示整数数列。
输出格式
共一行,包含m个整数,表示整数数列中前m小的数。
数据范围
1≤m≤n≤105,
1≤数列中元素≤109
输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3
C++ 代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int const HSIZE = 100005;
int h[HSIZE];
/*
数据量限制以考察floyd堆排序,建立小根堆;
使用 Floyd 下滤;
*/
void downFloyd(int x, int size) {
int smlIdx = x;
// 无子树的情况,即 h[x] 表示根节点;
if (2 * x > size) return;
// 有左子树的情况;
if (2 * x <= size && h[x] > h[2 * x]) smlIdx = 2 * x;
// 左右子树的情况;
if (2 * x + 1 <= size) {
if (h[2 * x] > h[2 * x + 1] && h[2 * x + 1] < h[x]) {
smlIdx = 2 * x + 1;
}
}
// 选择子树中较小者对调,逐层下滤;
if (smlIdx != x) {
swap(h[x], h[smlIdx]);
downFloyd(smlIdx, size);
}
}
int main() {
int n, m;
cin >> n >> m;
// 初始化存储堆的数组;
memset(h, 0, sizeof(h));
// 填充堆数组;
for (int i = 1; i <= n; i++) {
scanf("%d", &h[i]);
}
// Floyd 下溢,使得堆满足小根堆结构,即 父节点小于子节点;
for (int i = n / 2; i >= 0; i--) {
downFloyd(i, n);
}
// 基于小根堆进行输出;
while (m--)
{
cout << h[1]; // 输出堆顶;
if (m > 0) cout << ' ';
h[1] = h[n]; // 堆尾填充堆顶;
h[n] = 0; // 堆尾置为0;
downFloyd(1, --n); // 堆规模减一,再次下溢维护小根堆结构;
}
cout << endl;
return 0;
}