【C++】 C++ priority_queue 完全指南：优先队列的使用与手写实现

📌 相关专栏

• 【Linux专栏】
• 【C语言专栏】
• 【测试专栏】
• 【MySQL专栏】
• 【C++ 专栏】

📌 相关文章推荐

• 【C++】C++继承入门（下）：友元、静态成员与菱形继承的底层逻辑
• 【C++】 String 核心用法：构造、遍历、容量与优化技巧
• 【C++】手写双向链表：list容器模拟实现
• 【C++】模板初阶： 解析模板原理、实例化与特化

很高兴你点开这篇文章✨

这里会持续更新更多有用的内容，关注我，一起慢慢变好呀

👍 点赞 ⭐ 收藏 💬 评论

文章目录

• 前言
• 1. priority_queue 概述与核心概念
• • 1.1 堆的基本概念
  • 1.2 适配器要求
  • 1.3 容器适配器额属性
• 2. 基本接口使用
• • 2.1 常用接口
  • 2.2 默认大堆
  • 2.3 小堆（使用 greater）
• 3. 仿函数：自定义比较规则
• • 3.1 什么是仿函数？
  • 3.2 比较器的作用
• 4. 手写实现：堆的核心算法
• • 4.1 向上调整算法（AdjustUp）
  • 4.2 向下调整算法（AdjustDown）
  • 5.2 核心接口实现
• 6. 测试priority_queue模拟实现
• • 6.1 测试模拟实现的大堆
  • 6.2 测试小堆（使用 Greater）
  • 仿函数测试
• 7. 总结
• 🐾本文代码链接：

前言

priority_queue（优先队列）是 C++ 标准库中的容器适配器，它的底层是一个堆（默认是大堆），能够让我们以 O(log n) 的时间复杂度获取优先级最高的元素。

优先队列就像一个 VIP 服务队列：

• 普通队列：先来先服务
• 优先队列：优先级高的先服务（无论何时到达）

🐶 🐾 ✨ 🐾 🐶

1. priority_queue 概述与核心概念

1.1 堆的基本概念

优先队列的底层是完全二叉树，通过数组存储，利用父子节点下标关系维护堆结构 ：

父子节点下标公式：

• 已知孩子下标 child，父节点下标：father = (child – 1) / 2
• 已知父节点下标 father，左孩子下标：child = father * 2 + 1
• 右孩子下标：child = father * 2 + 2

1.2 适配器要求

priority_queue 作为容器适配器，底层容器需满足：

🐾STL 默认使用 vector 作为底层容器（空间连续，堆算法效率高），也可指定 deque。

1.3 容器适配器额属性

不直接存储数据，而是封装底层容器（vector、deque），并通过堆算法（make_heap,push_heap,pop_heap）来维护堆结构

🐶 🐾 ✨ 🐾 🐶

2. 基本接口使用

2.1 常用接口

• pirority_queue（）：构造一个空的优先队列，初始化后无任何元素，需通过push（x）插入数据

• priority_queue(first,last)：利用迭代器区间[first,last)中所有的元素初始化优先队列，初始化后会自动调整为堆结构

• empty（）：检测优先队列是否为空，若队列中无元素则返回true，存在元素返回false，常用于判断是否执行top（）或pop（）

• size（）：返回优先队列中有效元素的个数，可用于了解队列数据量，或配合循环控制 pop() 操作次数（如 Top K 问题中弹出前 K – 1 个元素）

• top（）；\\t返回堆顶元素的引用，大堆场景下返回队列中的最大值，小堆场景下返回最小值；需注意，调用前需用 empty() 确认队列非空，否则会触发未定义行为

• push（x）：将元素 x 插入优先队列的尾部，插入后会自动调用堆算法 (push_heap) 调整堆结构，确保队列仍满足大堆或小堆的排序规则

• pop（）：删除优先队列的堆顶元素，删除前会先通过堆算法（pop_heap）将堆顶元素交换到队列尾部，再执行删除；操作后需确保队列非空，且删除后仍保持堆结构

2.2 默认大堆

#include<queue>
using namespace std;

int main()
{
// 默认大堆：最大元素在顶部
priority_queue<int> pq1;
pq1.push(4);
pq1.push(7);
pq1.push(2);
pq1.push(5);
pq1.push(10);
pq1.push(8);

while (!pq1.empty())
{
cout << pq1.top() << " "; // 10 8 7 5 4 2
pq1.pop();
}
return 0;
}

2.3 小堆（使用 greater）

// 小堆：最小元素在顶部
priority_queue<int, vector<int>, greater<int>> pq2;
pq2.push(4);
pq2.push(7);
pq2.push(2);
pq2.push(5);
pq2.push(10);
pq2.push(8);

while (!pq2.empty())
{
cout << pq2.top() << " "; // 2 4 5 7 8 10
pq2.pop();
}

3. 仿函数：自定义比较规则

3.1 什么是仿函数？

仿函数是一个重载了 operator() 的类，实例化后的对象可以像函数一样使用：

// 仿函数示例
template<class T>
struct Less
{
bool operator()(const T& x, const T& y)
{
return x < y; // x < y 时返回 true
}
};

template<class T>
struct Greater
{
bool operator()(const T& x, const T& y)
{
return x > y; // x > y 时返回 true
}
};

void test_Functor()
{
Less<int> LessFunc;

// LessFunc(1, 2) 本质是对象调用 operator()
cout << LessFunc(1, 2) << endl; // 1（true）
cout << LessFunc.operator()(1, 2) << endl; // 等价写法
}

3.2 比较器的作用

• Less<T> ：用于大堆 ，父节点 < 子节点时交换
• Greater<T> ：用于小堆 ，父节点 > 子节点时交换

🐶 🐾 ✨ 🐾 🐶

4. 手写实现：堆的核心算法

4.1 向上调整算法（AdjustUp）

使用场景 ：push 插入新元素后，将其向上调整到正确位置。

namespace MyPriorityQueue
{
//模板声明
template<class T, class Container = vector<T>, class Compare = Less<T>>
// T：存储的元素类型（int、stirng..）
// Container： 底层容器（默认vector，需支持随机访问和尾部操作）
// Compare：比较器（默认Less，即大堆）

//自定义优先队列类，接口与STL完全对齐
class priority_queue
{
public:
//向上调整算法(已知孩子位置推算父亲位置)
//AdjustUp:向上调整，用于插入
void AdjustUp(size_t child)//访问下标
{
// 实例化比较器，用于判断优先级
Compare com;

//完全二叉树的父子下表公式，通过孩子下标计算父节点下标
size_t father = (child – 1) / 2;

//当child等于0说明已经调整到头节点
while (child > 0)
{
//if (_con[child] > _con[father])
//比较
if (com(_con[father], _con[child]))//需要注意Less是建立大堆，但是比较大小是 < ,父亲和孩子的顺序不要错
{
//1.若子节点>父节点：交换两者，然后将父节点作为新的孩子，继续向上调整

swap(_con[child], _con[father]);
child = father;
father = (child – 1) / 2;
}
else
{
//2.若子节点<=父节点：满足堆结构，直接跳出循环

break;
}
}

🐾 以大堆为例，插入新元素后向上调整

4.2 向下调整算法（AdjustDown）

使用场景 ：pop 删除堆顶元素后，将新堆顶元素向下调整。

namespace MyPriorityQueue
{
//模板声明
template<class T, class Container = vector<T>, class Compare = Less<T>>
// T：存储的元素类型（int、stirng..）
// Container： 底层容器（默认vector，需支持随机访问和尾部操作）
// Compare：比较器（默认Less，即大堆）

//自定义优先队列类，接口与STL完全对齐
class priority_queue
{
public:
//向下调整算法(已知父亲位置推算孩子位置)
//AdjustDown:向下调整，用于删除
void AdjustDown(size_t father)//访问下标
{
// 实例化比较器，用于判断优先级
Compare com;

//通过父节点下标计算左孩子下标（father*2+1）,右孩子下标（father*2+2）
size_t child = father * 2 + 1;

//孩子下标超出数组范围（已到叶子节点）
while (child < _con.size())
{
//if ((child + 1) < _con.size() && _con[child] < _con[child + 1])

//(child+1)<_con.size：先判断右孩子是否存在且值更大
//若右孩子存在，将child指向右孩子（保证child始终是两个孩子中的较大者）
if ((child + 1) < _con.size() && com(_con[child], _con[child + 1]))
{
child += 1;
}

//if (_con[father] < _con[child])
//大堆顶规则校验
//1.若父节点 < 较大子节点：交换两者，然后将父节点作为新的父节点，继续向下调整
//2.若父节点 >= 较大子节点：满足堆结构，直接跳出循环

if (com(_con[father], _con[child]))
{
swap(_con[father], _con[child]);
father = child;
child = father * 2 + 1;
}
else
{
break;
}
}
}

5.2 核心接口实现

// 插入数据(入优先级队列)
void push(const T& x)
{
_con.push_back(x); // 1. 尾插
AdjustUp(_con.size() – 1); // 2. 向上调整
}

// 获取堆顶元素(队头数据)
const T& top()
{
return _con[0];
}

// 删除堆顶元素(出优先级队列)
void pop()
{
swap(_con[0], _con[_con.size() – 1]); // 1. 交换首尾
_con.pop_back(); // 2. 尾删
AdjustDown(0); // 3. 向下调整
}

// 获取元素个数
size_t size()
{
return _con.size();
}

// 判空
bool empty()
{
return _con.size() == 0;
}

🐶 🐾 ✨ 🐾 🐶

6. 测试priority_queue模拟实现

6.1 测试模拟实现的大堆

void test_priority_queue()
{
// 默认大堆
MyPriorityQueue::priority_queue<int> pq1;
pq1.push(4);
pq1.push(7);
pq1.push(2);
pq1.push(5);
pq1.push(10);
pq1.push(8);

while (!pq1.empty())
{
cout << pq1.top() << " "; // 10 8 7 5 4 2
//如果没用优先级（priority_queue）:4 7 2 5 10 8
pq1.pop();
}
cout << endl;
}

6.2 测试小堆（使用 Greater）

void test_priority_queue()
{
// 小堆：使用 Greater 比较器
MyPriorityQueue::priority_queue<int, vector<int>, Greater<int>> pq2;//调整成默认是小的优先级高(小堆—最小的元素在顶部)
pq2.push(4);
pq2.push(7);
pq2.push(2);
pq2.push(5);
pq2.push(10);
pq2.push(8);

while (!pq2.empty())
{
cout << pq2.top() << " "; // 2 4 5 7 8 10
// 如果没用优先级队列（priority_queue）:4 7 2 5 10 8
pq2.pop();
}
cout << endl;
}

仿函数测试

void test_Functor()
{
//函数对象
Less<int> LessFunc;

//我们会发现 LessFunc(1, 2) 在结构上是非常类似函数的使用
//但实际上就是一个对象调用了重载 operator() 的结果
cout << LessFunc(1, 2) << endl;//[1,2)

//也可以写出下面更加清晰的结构：
cout << LessFunc.operator()(1, 2) << endl;
}

int main()
{
test_Functor();
return 0;
}

🐶 🐾 ✨ 🐾 🐶

7. 总结

🐾 priority_queue 的核心知识点：

🐾 时间复杂度对比

🐾 适用场景

• Top K 问题（最大的 K 个元素）
• 任务调度（优先级高的任务先执行）
• 合并 K 个有序链表
• 求数据流中的中位数

🐶 🐾 ✨ 🐾 🐶

🐾本文代码链接：

https://gitee.com/ayidyy/cyvyan11/commit/f30ba9f3b231855517b1ceb07b737a14883866ee

谢谢你看到这里呀

如果喜欢这篇内容，点个关注，下次更新不迷路✨

👍 点赞 ⭐ 收藏 💬 评论