C++优先队列详解

zyz610

2026-06-28 22:34:20

发布于：广东

6阅读

0回复

0点赞

C++ 优先队列 (priority_queue) 详解

什么是优先队列

优先队列是一种特殊的队列，它并不按先进先出的顺序弹出元素，而是按照优先级弹出元素。每次弹出的都是当前容器中优先级最高的元素。

从数据结构的角度看，优先队列通常使用堆来实现，最常见的实现是二叉堆。在 C++ 标准库中，priority_queue 就是一个基于堆的容器适配器。

priority_queue的基本使用

priority_queue 定义在头文件 <queue> 中，
使用时需要使用万能头或导入<queue>
priority_queue 的功能和queue 差不多

push(x) : 将元素 x 插入队列，时间复杂度 O(log n)
pop() : 弹出优先级最高的元素，时间复杂度 O(log n)
top() : 返回优先级最高的元素（只读），时间复杂度 O(1)
empty() : 判断队列是否为空
size() : 返回元素个数

注意：与普通队列 queue 不同，priority_queue 的“队首”是 top() 而不是 front()；同样也没有 back() 方法，因为只关心优先级最高的元素。

优先队列的优先级

priority_queue 有两中：

priority_queue<int,vector<int>,less<int> > q;           //大的在前(大根堆)     less<int> 可以不加
priority_queue<int,vector<int>> q;
priority_queue<int,vector<int>,greater<int> > q;        //小的在前(小根堆)

具体使用哪个根据题意

练习

P1168 中位数是一道非常经典的优先队列题，建议做一下
题意：
输入n个数，输出前奇数个数的中位数。
分析：
普通思路暴力肯定会超时，所以要用优先队列。
思路：
把序列分成两个优先队列，一个大根堆，一个小根堆

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    priority_queue<int>da;                              //大根堆
    priority_queue<int,vector<int>,greater<int>>xiao;   //小根堆
    for (int i=1;i<=n;i++) 
	{
        int x;
        cin>>x;                                          //输入要插入的值
        if(da.empty()||x<=da.top())                      //判断进入大根堆还是小顶堆
		{
            da.push(x);
        }
		else 
		{
            xiao.push(x);
        }
        if(da.size()>xiao.size()+1)                       //判断两堆数字个数
		{
            xiao.push(da.top());                     
            da.pop();
        }
		else if(xiao.size()>da.size()) 
		{
            da.push(xiao.top());
            xiao.pop();
        }
        if(i%2==1) 
		{
            cout<<da.top()<<endl;                         //输出
        }
    }
    return 0;
}