网站导航
> 技术文档 > 【C++强基篇】学习C++就看这篇---＞STL之priority_queue使用及实现

【C++强基篇】学习C++就看这篇---＞STL之priority_queue使用及实现

网友: 技术文档 2025-09-03 02:53:15

主页：HABUO🍁主页：HABUO

🍁C++入门到精通专栏🍁

🍁如果再也不能见到你，祝你早安，午安，晚安🍁

目录

📕一、priority_queue的介绍  

📕二、priority_queue的使用    

📂 头文件与命名空间 

✨2.1 构造与初始化   

✨2.2 元素访问  

✨2.3 修改操作 

✨2.4 容量查询 

✨2.5 关键特性与注意事项 

2.5.1. 底层容器要求

2.5.2. 比较函数（Compare）（仿函数）

2.5.3. 时间复杂度

2.5.4. 注意事项 

📕二、priority_queue的简单模拟实现    

📕三、总结   

前言： 

上篇博客我们了解了STL中的适配器stack、queue，本篇博客我们继续对STL中的组件进行学习，今天我们要学习一个新的适配器qriority_queue，学习思路与前面还是一样的，第一步就是：是什么怎么用，第二步就是我们能不能自己实现一个简单的priority_queue（即为了了解它的底层原理），经过这两步的学习之后，应对绝大多数的场景已经足够使用。和stack、queue是一样的，priority_queue学起来还是比较轻松的，只是有一点是与前面是不同的，它们引入了一个仿函数的概念，下面我们会详细的进行介绍，希望大家有所收获！

📕一、priority_queue的介绍  

std::priority_queue 是 C++ 标准模板库提供的优先队列容器适配器，它基于堆数据结构实现，能够高效地获取和删除队列中的最大（或最小）元素。默认情况下，它维护一个最大堆（队首总是最大元素）。

🌟 核心特性

  • 优先级访问：队首元素始终是优先级最高的元素

  • 容器适配器：基于底层容器实现（默认 std::vector）

  • 堆结构：使用二叉堆实现高效优先级管理

  • 受限接口：只暴露优先级队列相关操作

  • 无迭代器：不支持元素遍历

📕二、priority_queue的使用    

📂 头文件与命名空间 

#include  // 与 queue 相同头文件using namespace std; // 或显式使用 std::priority_queue

需要注意的是，priority_queue是在queue头文件当中的。 

与stack、queue适配器极其相似，主要使用：构造与初始化、元素访问、修改操作、容量查询。由于使用起来很简单，总体来说总共有下面这些接口。下面我们来一一介绍。    

函数声明 接口说明 priority_queue() / priority_queue(first, last)（重点） 构造一个空的优先级队列，或用迭代器区间 [first, last) 构造 empty()（重点） 检测优先级队列是否为空，是返回 true，否则返回 false top()（重点） 返回优先级队列中最大（或最小）元素，即堆顶元素 push(x)（重点） 在优先级队列中插入元素 x pop()（重点） 删除优先级队列中最大（或最小）元素，即堆顶元素

✨2.1 构造与初始化   

// 默认构造（最大堆，队首为最大元素）std::priority_queue pq1; // 自定义底层容器（deque）std::priority_queue<int, std::deque> pq2; // 创建最小堆（队首为最小元素）std::priority_queue<int, std::vector, std::greater> pq3; // 使用已有容器初始化std::vector vec = {3, 1, 4, 1, 5};std::priority_queue pq4(vec.begin(), vec.end());// 自定义比较函数auto cmp = [](int a, int b) { return a % 10 > b % 10; };std::priority_queue<int, std::vector, decltype(cmp)> pq5(cmp);

注意看：

// 创建最小堆（队首为最小元素）
std::priority_queue<int, std::vector, std::greater> pq3; 

其中greater就是设置的仿函数，下面章节会进行详细介绍，需要注意，底层实现上仿函数的参数是设置在第三个，因此设置时，第二个参数vector也就是必须要写了。

✨2.2 元素访问  

pq1.push(10); // 插入元素int top_val = pq1.top(); // 访问队首元素（优先级最高）// 注意：空队列调用 top() 是未定义行为

✨2.3 修改操作 

pq1.push(20); // 插入元素（O(log n)）pq1.pop(); // 删除队首元素（O(log n)）

✨2.4 容量查询 

bool empty = pq1.empty(); // 判断队列是否为空size_t size = pq1.size(); // 返回元素数量

✨2.5 关键特性与注意事项 

2.5.1. 底层容器要求

操作 所需容器方法 front() front() push_back() push_back() pop_back() pop_back()

有效底层容器：

  • std::vector（默认）

  • std::deque

  • ❌ std::list（不支持 pop_back() 高效实现）

// 使用 deque 作为底层容器std::priority_queue<int, std::deque> deque_pq;

2.5.2. 比较函数（Compare）（仿函数）

  • 默认比较器：std::less → 最大堆（队首为最大元素）

  • 最小堆：使用 std::greater → 队首为最小元素

  • 自定义比较器：必须实现严格弱序

// 自定义比较函数（按字符串长度排序）struct LengthCompare { bool operator()(const std::string& a, const std::string& b) { return a.length() < b.length(); // 长度大的优先级高 }};std::priority_queue<std::string, std::vector, LengthCompare> str_pq;

2.5.3. 时间复杂度

操作 时间复杂度 说明 push() O(log n) 插入并调整堆 pop() O(log n) 删除堆顶元素 top() O(1) 访问堆顶 建堆 O(n) 通过迭代器构造时

push、pop时涉及前面我们学到的堆的向上与向下调整算法，下面底层实现时，我们再进行回顾 

2.5.4. 注意事项 

  • 空队列检查：调用 top() 或 pop() 前必须检查 empty()

  • 无清空方法：需手动弹出元素清空队列

    while (!pq1.empty()) pq1.pop();

  • 元素顺序：除堆顶外，其他元素顺序不确定

  • 自定义类型：存储自定义类型时需提供比较函数（仿函数）

    struct Task { int priority; std::string name;};auto cmp = [](const Task& a, const Task& b) { return a.priority < b.priority; // 大顶堆};std::priority_queue<Task, std::vector, decltype(cmp)> task_pq(cmp);

大家可以通过下面这道题小试牛刀一番 

数组中的第K个最大元素 

📕二、priority_queue的简单模拟实现    

priority_queue底层实现原理就是通过堆操作来完成的，里面涉及了两个重要的算法：堆向上调整与向下调整算法，而这两个算法的核心就是要清楚堆中父亲和孩子的关系：孩子=父亲*2+1。或者父亲=（孩子-1）/ 2

namespace hab{template<class T , class Container = vector>class priority_queue{public:void AdjustUp(int child){int parent = (child - 1) / 2;while (child > 0){if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void AdjustDown(int root){int parent = root;int child = parent * 2 + 1;//计算的是左孩子while (child < _con.size()){//判断哪个孩子大if (child + 1  _con[child])++child;if (_con[child] > _con[parent]){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}void push(const T& x){//O(logN)_con.push_back(x);AdjustUp(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();//O(logN)AdjustDown(0);}T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};}

上面写的是一个没有仿函数的一个简单优先级队列，这样就存在一个问题，默认的是大数优先级高
那我们要是想小数优先级高怎么办？
现有的方法是不是只能再拷贝一份代码，将向上调整算法与向下调整算法里的符号改动一下
但是这样的代码复用率不高
因此仿函数就是解决这样的问题的 

仿函数：也称为函数对象 (Function Object)，本质上是一个行为类似函数的类或结构体。它通过重载函数调用运算符 operator() 来实现这一点。 

基本语法：

class MyFunctor {public: // 重载函数调用运算符 operator() return_type operator() (parameter_list) const; // 常加 const 表示不修改对象状态 // 或者不加 const，如果仿函数需要修改内部状态};

事实上它就是一个类或者结构体，里面就是重载了一个 operator()函数，拿上述的问题为例，我们想让一个类，只通过变换模板参数就可以实现一个大堆或小堆，但是里面仅仅只改了部分符号而已我们就可以通过这样的一个仿函数来实现，如下所示：

 templatestruct less {bool operator()(const T& x1, const T& x2){return x1 < x2;}};templatestruct greater {bool operator()(const T& x1, const T& x2){return x1 > x2;}};

怎么在那个类里面使用呢？如下： 

template<class T, class Container = vector, class Compare = less>class priority_queue{public:void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}elsebreak;}}void AdjustDown(int root){Compare com;int parent = root;int child = parent * 2 + 1;//计算的是左孩子while (child < _con.size()){//判断哪个孩子大if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))++child;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent = child;child = parent * 2 + 1;}elsebreak;}}

可以发现对比上述的底层实现，那些比较符号换成了 com(_con[parent], _con[child])等，事实上这个本质就是条用了那个重载的函数，通过模板参数的修改调用不同类的重载函数，实现不同的功能

📕三、总结    

学习到此，我们可以对前面学习的STL中的相关知识进行一个小结：

容器:     string/vector/list/deque    (序列式容器)
适配器: stack/queue/priority_queue
洪代器: iterator/const iterator/reverse iterator/const_reverse_iterator
算法:     sort/find/reverse
仿函数: less/greater

本篇博客我们了解学习了priority_queue，std::priority_queue 是 C++ 的优先队列适配器，默认用最大堆，头文件 。常用接口：push/pop/top/empty/size，复杂度 O(log n)。支持自定义底层容器、比较函数或仿函数，如 greater 得最小堆。底层用堆，建堆 O(n)，需容器支持 push_back/pop_back/front。模拟实现：向上/向下调整保持堆序；仿函数 less/greater 实现大小比较。 希望大家有所收获！

网络标签：

相关问题