AcWing 838. 堆排序 C++
原题链接
简单
作者:
LaChimere
,
2021-05-22 09:28:47
,
所有人可见
,
阅读 241
C++
#include <iostream>
using namespace std;
const int MAXSIZE = 100010;
int n, m, a[MAXSIZE];
void sink(int k) {
while (2*k <= n) {
int i = 2*k;
if (i < n && a[i] > a[i+1]) {
++i;
}
if (a[k] <= a[i]) {
break;
}
swap(a[k], a[i]);
k = i;
}
}
void buildHeap() {
for (int k = n/2; k > 0; --k) {
sink(k);
}
}
int pop() {
int val = a[1];
swap(a[1], a[n--]);
sink(1);
return val;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", a+i);
}
buildHeap();
while (m--) {
printf("%d ", pop());
}
return 0;
}