C++：堆排序

堆排序

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

输入格式

第一行包含整数n和m
第二行包含n个整数，表示整数数列

输出格式

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

数据范围

$1\le m\le n\le 10^5$
$1\le numofelementsinsequence\le 10^9$

输入样例

5 3
4 5 1 3 2

输出样例

1 2 3

问题分析

堆的基本操作
1.插入一个数 heap[++size] = x; up(size);
2.求集合中的最小值 heap[1];
3.删除最小值 heap[1] = heap[size]; size--; down(1);
4.删除任意一个元素 heap[k] = heap[size]; size--; down(k); up(k);
5.修改任意一个元素 heap[k] = x; down(k); up(k);

AC代码

#include<iostream>
#include<algorithm>
using namespace std;const int N = 1e5 + 10;int n, m;
int h[N], sz;void down(int u) {int t = u;if(u * 2 <= sz && h[u * 2] < h[t]) t = u * 2;if(u * 2 + 1 <= sz && h[u * 2 + 1] < h[t]) t = u * 2 + 1;if(u != t) {swap(h[u], h[t]);down(t);}
}int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++) scanf("%d", &h[i]);sz = n;for(int i = n / 2; i; i--) down(i);while(m--) {printf("%d ", h[1]);h[1] = h[sz];sz--;down(1);	}return 0;
}