当前位置：首页 > news >正文

C++从入门到起飞之——priority_queue(优先级队列) 全方位剖析！

news 2025/6/27 12:37:35

🌈个人主页：秋风起，再归来~
🔥系列专栏：C++从入门到起飞
🔖克心守己，律己则安

1、priority_queue的介绍

2、priority_queue的使用

3、priority_queue的模拟实现

3.1、仿函数的介绍

3.2、模拟实现源码

4、完结散花

1、priority_queue的介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

>empty()：检测容器是否为空

>size()：返回容器中有效元素个数

>front()：返回容器中第一个元素的引用

>push_back()：在容器尾部插入元素

>pop_back()：删除容器尾部元素

5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue 类实例化指定容器类，则使用vector。

6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

2、priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue。注意：默认情况下priority_queue是大堆。

3、priority_queue的模拟实现

3.1、仿函数的介绍

在之前的文章中我提到过关于sort第三个参数的问题，当时我称他为比较器，事实上它更仿函数有关！

仿函数其实就是一个类里面进行了操作符（）的重载，我们用这个类实例化一个对象再调用它重载的（）就可以比较两个元素的大小！

下面举一个简单的示例代码：

template<class T>
class compareLess
{
public:bool operator()(const T& a1,const T& a2){return a1 < a2;}
};int main()
{compareLess<int> less;int a = 30;int b = 20;cout<<less.operator()(a,b)<<endl;return 0;
}

//cout<<less.operator()(a,b)<<endl;
cout<<less(a,b)<<endl;

重载函数的调用可以简化为 less(a,b)，我们会发现它的调用形式和函数非常相像，不同的是less是我们实例化出来的对象的名字，并不是函数名，因此，我们称其为仿函数！

现阶段我们看到仿函数看起来非常简单，确实如此，不过，我们在后面会遇到和仿函数有关的更为复杂的内容！

好啦，我们再来看到优先级队列，我们会发现它的模版参数里面也有仿函数的身影，原因也很简单，我们知道优先级队列就是堆，那我们在实现堆的时候必然会用到向上和向下调整的算法。而这些算法也一定会有元素的大小比较，如果我们在类里面实现的是一个大堆，那我们下次要用到小堆的时候怎么办呢！难道临时打电话给程序员叫他修改一下比较符号吗？显然不可能，难道实现俩个类吗，这两个类的代码高度相似，只有一些比较大小的符号不同，这样做并不合理。

这时候我们就可以通过传递比较器的方法来解决这个问题了！

//向上调整
void AdjustUp()
{//用比较器实例化一个对象compare comp;int child = con.size() - 1;int parent = (child - 1) / 2;while (child > 0){//仿函数取大向上调整if (comp(con[parent], con[child])){swap(con[child], con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}

在优先级队列实例化出对象之前，我们不知道你具体的比较逻辑！只有使用者在传递模版参数之后才可以确定！

3.2、模拟实现源码

这篇文章的主要目的是让我们初步了解仿函数并熟悉priority_queue，至于priority_queue的模拟实现其实非常简单（如果我们之前对数据结构中的堆学的还不错的话，这两个向上和向下调整算法也是手到擒来的！）下面我就直接给源码给大家参考一下了！

#pragma once#include<iostream>
#include<algorithm>
#include<list>
#include<vector>
#include<deque>using namespace std;namespace my_priority_queue
{//仿函数（比较器）template<class T, class container = vector<T>, class compare = less<T>>class priority_queue{public://元素数量size_t size(){return con.size();}//判空bool empty(){return con.size() == 0;}//向上调整void AdjustUp(){//用比较器实例化一个对象compare comp;int child = con.size() - 1;int parent = (child - 1) / 2;while (child > 0){//仿函数取大向上调整if (comp(con[parent], con[child])){swap(con[child], con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}//入栈void push(const T& val){con.push_back(val);//向上调整AdjustUp();}//向下调整void AdjustDown(){compare comp;int parent = 0;int child = parent * 2 + 1;//左孩子while (child < con.size()){//如果右孩子更大就更新孩子if ((child < con.size() - 1 )&& comp(con[child ], con[child+1])){child++;}//仿函数向下调整if (comp(con[parent], con[child])){swap(con[child], con[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//出栈void pop(){swap(con[0], con[con.size() - 1]);con.pop_back();AdjustDown();}//取优先级高元素const T& top(){return con[0];}private:container con;};}