STL队列queue的扩展——优先队列

时间:2021-08-02 15:14:51

STL队列queue的扩展——优先队列

1. 优先队列的使用

优先队列有类似于堆的作用,因此,优先队列也分为大根堆和小根堆

队列中的元素会自动进行排序

接下来谈谈它们的使用方法:


(1).定义

1.priority_queue<int> q 定义一个整型的大根堆q

2.priority_queue<int,vector<int>,greater<int> > q 定义一个整型的小根堆q


(2).插入和弹出

1.q.push(元素)把一个元素压入队首

2.q.pop()弹出队尾元素


(3).引用

1.q.top()返回堆顶元素


(4).其他

1.q.empty()判断是否为空

2.q.size()返回队中元素个数


e.g.

输入n个数,由小到大排序后输出(优先队列实现)


#include<iostream>
#include<queue>
#include<cstdio>
using namespace std;
priority_queue<int,vector<int>,greater<int> > a;
int k[100005];
int main()
{

    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&k[i]);
        a.push(k[i]);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d ",a.top());
        a.pop();
    }
    return 0;
}