AcWing 838. 堆排序(优先队列)
原题链接
简单
作者:
qiao
,
2022-08-17 15:34:27
,
所有人可见
,
阅读 226
C++ 代码
#include<bits/stdc++.h>
using namespace std;
/*
greater: left > right
less: left < right
对于up函数,如果比较值为1则上浮
而父节点较小,因此父节点为L,新节点为R
对于大根堆,p>s,为了维持这个趋势(或者说让混乱情况转变为此趋势)则需要
令p>s(即greater)比较值为0,即less
因此大根堆为less 小根堆为greater
*/
int main()
{
priority_queue<int> q1;//对于基础类型 默认是大根堆(递减)值大的先出队,如果是数组存储数,根结点为1
//等同于 priority_queue<int, vector<int>, less<int> > a;
priority_queue<int, vector<int>, greater<int> >q2;
//小根堆(递增),值小的先出队
priority_queue<int, vector<int>, greater<int> > h;
int n, m; cin >> n >> m;
while (n--)
{
int x; cin >> x;
h.push(x);
}
for (int i = 1; i <= m; i++)
{
cout << h.top() << " ";
h.pop();
}
}