POJ-数据结构-优先队列模板

优先队列模板

优先队列是用堆实现的，所以优先队列中的push()、pop()操作的时间复杂度都是O(nlogn)。

优先队列的初始化需要三个参数，元素类型、容器类型、比较算子。

需要熟悉的优先队列操作：

q.top() 访问堆顶
q.push() 入堆
q.pop() 出堆
不同类型元素的优先级设置
定义堆需要注意最后两个> >之间有一个空格

数据结构

priority_queue < int, vector<int>, less<int> > q; // 大顶堆——堆顶为大数

priority_queue < int, vector<int>, greater<int> > q; // 小顶堆——堆顶为小数

例-百练4078：实现堆结构

AC代码

#include<iostream>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

int main()

{

    priority_queue < int, vector<int>, greater<int> >q;

    int m, t, x, top;

    cin >> m;

    while (m--)

    {

        cin >> t;

        if (t == )

        {

            cin >> x;

            q.push(x);

        }

        if (t == )

        {

            top = q.top();

            cout << top << endl;

            q.pop();

        }

    }

    return ;

}

巴特西

POJ-数据结构-优先队列模板

最新文章

热门文章