AcWing 838. 堆排序
原题链接
简单
作者:
szywdwd
,
2021-05-24 14:30:13
,
所有人可见
,
阅读 192
// #include <iostream>
// #include <vector>
// #include <queue>
// using namespace std;
// int main()
// {
// priority_queue<int, vector<int>, greater<int>> heap;// 默认是大顶堆,可设置比较器为小顶堆
// int n, m;
// cin >> n >> m;
// while(n--) {
// int tmp;
// cin >> tmp;
// heap.push(tmp);
// }
// while(m--) {
// cout << heap.top() << ' ';
// heap.pop();
// }
// return 0;
// }
// 堆操作:
// 1.插入一个数 heap[++sizeOfHeap] = x; up(sizeOfHeap);
// 2.求集合中的最小值 heap[1];
// 3.删除最小值 heap[1] = heap[sizeOfHeap--]; down(1);
// 4.删除任意一个元素 heap[k] = heap[sizeOfHeap--]; down(k); up(k);// down, up总有一个会执行,让修改后的结点走到符合堆定义的地方
// 5.修改任意一个元素 heap[k] = x; down(k); up(k);
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n, m;
int h[N], sizeOfHeap;
// x是下标
void down(int x) {
int t = x;
// 找到三者之间最小值的下标t
if(2 * x <= sizeOfHeap && h[2 * x] < h[t]) t = 2 * x;
if(2 * x + 1 <= sizeOfHeap && h[2 * x + 1] < h[t]) t = 2 * x + 1;
// 如果最小值下标不为三者其中的根的下标
if(t != x) {
swap(h[x], h[t]);// 交换根与最小的儿子的值
down(t);// 继续往下
}
}
int main()
{
cin >> n >> m;
sizeOfHeap = n;
for(int i = 1; i <= n; ++i)
cin >> h[i];
// 从最右下的非叶结点开始调整数组使之成为堆
for(int i = n / 2; i; --i)
down(i);
while(m--) {
cout << h[1] << ' ';
h[1] = h[sizeOfHeap--];
down(1);
}
return 0;
}