往期内容回顾  

            deque类型使用和介绍（初识）

           Queue介绍和使用  

            Stack介绍和使用

---

C++ priority_queue（优先队列）详解

前言

        优先队列（priority queue）是一种按“优先级”而不是插入顺序服务的抽象数据结构。和普通队列（FIFO）不同，优先队列每次取出的都是当前优先级最高（或最低）的元素。C++ 标准库通过 std::priority_queue 提供了基于堆（heap）的高效实现。优先队列在许多算法中非常常见：Dijkstra、A*、事件驱动仿真、流数据的 top-k 问题、滑动窗口的单调队列变体等。

---

主要内容概览

1. 1、priority_queue 是什么？（接口与语义）

2. 2、底层实现（堆：binary heap + make_heap/push_heap/pop_heap）

3. 3、常用操作与复杂度（push/pop/top/从范围构造）

4. 4、自定义比较函数/最小堆与最大堆、pair 的用法（Dijkstra 风格）

5. 5、与 queue/stack 的区别（语义与底层）

6. 6、常见坑、性能与实践建议（稳定性、迭代器、线程安全等）

7. 7、用 make_heap 手工实现优先队列的例子

8. 总结

---

一、std::priority_queue是什么？接口与语义

        std::priority_queue 是一个容器适配器（adapter），常见定义形式：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<T>
> class priority_queue;

• 默认底层容器是 std::vector<T>（因为需要随机访问迭代器以实现 heap 操作）。

• 默认比较器 std::less<T> 会产生一个 最大堆（max-heap）：top() 返回当前最大元素。

• 若想要 最小堆（min-heap），传入 std::greater<T>：priority_queue<int, vector<int>, greater<int>> pq;，top() 返回最小元素。

常用成员函数：

• empty()、size()

• top()：返回优先级最高的元素（O(1)）

• push(const T&) / push(T&&)：插入（O(log n)）

• emplace(args...)：原地构造并插入（O(log n)）

• pop()：弹出最高优先级元素（O(log n)）

• 构造器支持从范围构造：priority_queue(it_begin, it_end)（内部使用 make_heap，O(n) 构建）

注意：pop() 不返回被弹出的元素 —— 需要先 top() 拿值再 pop()。

---

二、底层实现：binary heap（与 make_heap / push_heap /pop_heap）

        std::priority_queue 底层基于堆（heap）算法，常见实现是二叉堆（binary heap），用一个连续的数组（vector）表示树结构。核心思想：

• 父子关系通过下标计算：对于索引 i，左子 2*i+1、右子 2*i+2（0-based）。

• push：把新元素放在数组末尾，然后向上“sift-up”来维持堆序（O(log n)）。

• pop：把堆顶与末尾交换并删除末尾，然后对新堆顶做“sift-down”修复（O(log n)）。

• 从一个数组范围构建堆可用 std::make_heap，其平均复杂度为 O(n)（比逐次 push 的 O(n log n) 好）。

标准库提供的 heap 算法：

• std::make_heap(begin, end)：把区间变为堆（默认是 max-heap）

• std::push_heap(begin, end)：在末端新增元素后调整为堆

• std::pop_heap(begin, end)：把堆顶移动到末端，并重新调整堆（之后通常 pop_back() 删除元素）

priority_queue 正是对这些操作的封装：内部维护 vector<T> c;，对外提供 push/pop/top 等。

---

三、常用操作与复杂度

• top()：O(1)（读取 c.front()）

• push() / emplace()：O(log n)（sift-up）

• pop()：O(log n)（sift-down）

• 构造（从区间）：O(n)（make_heap）

• 内存：底层是 vector<T> 连续存储，拥有 capacity() 机制，push 可能触发重新分配

示例代码（基本用法）：

#include <queue>
#include <vector>
#include <functional>
#include <iostream>

int main(){
    std::priority_queue<int> pq;        // max-heap
    pq.push(5); pq.push(1); pq.push(7);
    std::cout << pq.top() << "\n";      // 7
    pq.pop();
    std::cout << pq.top() << "\n";      // 5

    // min-heap
    std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;
    minpq.push(5); minpq.push(1); minpq.push(7);
    std::cout << minpq.top() << "\n";   // 1
}

---

四、自定义比较函数与复杂元素（pair / struct）

常用模式：Dijkstra 中的 pair<distance,node>，希望按距离最小优先出队。

方法 A：使用 greater<pair<int,int>>（pair 的 < 比较按 first then second）

using P = std::pair<int,int>;
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
pq.emplace(0, start);

方法 B：自定义比较器（更明确）

struct NodeCmp {
    bool operator()(const P& a, const P& b) const {
        return a.first > b.first; // 返回 true 表示 a 的优先级低于 b
    }
};
std::priority_queue<P, std::vector<P>, NodeCmp> pq;

注意比较器方向：Compare 在容器模板里定义为“比较器对象”，当 Compare(a,b) 为 true 时，通常意味着 a 的优先级低于 b（会被放到 heap 的下方）。这有点绕，实战中牢记两条简洁规则会更安全：

• std::less<T> → max-heap（默认）

• std::greater<T> → min-heap

等优先级的稳定性：堆 不是稳定 的，equal-priority 元素的相对顺序不保证。

---

五、priority_queue 与 queue/stack 的区别

特性	queue（FIFO）	priority_queue（Heap）
出队策略	先进先出	按优先级（最大或最小）
底层容器限制	默认 deque，底层需支持 push_back/pop_front	默认 vector，需要随机访问容器（vector/deque）
接口	push/pop/front/back	push/pop/top
典型用途	队列、BFS、任务队列	Dijkstra、事件仿真、top-k、调度
复杂度	push/pop O(1)	push/pop O(log n)
可遍历性	queue 无迭代器（需底层容器），priority_queue 也无迭代器	两者都不直接提供迭代遍历接口

总结：queue 强调插入顺序（FIFO），priority_queue 强调按优先级服务（使用 heap 实现），它们在语义和性能特性上差异明显。

---

六、常见坑与实践建议

1. top()/pop() 的用法

   pop() 不返回值。正确顺序是：

auto val = pq.top();
pq.pop();

1. 切勿 pq.pop(); use pq.top() afterwards — top() will then reflect next element or UB if empty.

2. 空队列上 top()/pop() 是未定义行为，应先 empty() 检查。

3. 比较器方向容易混淆：记住 less → max-heap，greater → min-heap。对于复杂类型，测试一下小示例确保方向正确。

4. 堆不稳定：当优先级相同需要稳定性时，额外携带时间戳或序号。

5. 修改堆中间元素：没有直接 API 修改优先级。常见做法是“惰性删除”：插入新优先级的元素，并在 pop 时忽略旧（已过期）条目；或者使用支持 decrease-key 的数据结构（如斐波那契堆，或可自行维护 index heap）。

6. 迭代器/引用失效：底层是 vector（连续内存），push 可能导致 vector reallocate，使得对元素的指针/引用失效。

7. 线程安全：标准容器非线程安全。并发场景请自行加锁或使用并发队列实现。

8. 性能思考：

   • push/pop 是 O(log n)，当 n 很大且频繁操作时注意开销。

   • 如果只是“需要 top-k”且数据流很大，常用技巧是维护一个大小为 k 的 min-heap（greater），复杂度为 O(n log k)。

---

七、用 make_heap手工实现优先队列（底层演示）

        priority_queue 其实就是对 heap 算法的封装。下面展示用 vector + heap 操作自己实现简化版优先队列。

#include <vector>
#include <algorithm>
#include <iostream>

int main(){
    std::vector<int> v = {5, 1, 7, 3};
    std::make_heap(v.begin(), v.end()); // make max-heap
    std::cout << v.front() << "\n";     // max element

    // push 6
    v.push_back(6);
    std::push_heap(v.begin(), v.end()); // fix heap
    std::cout << v.front() << "\n";

    // pop max
    std::pop_heap(v.begin(), v.end());  // moves max to back
    v.pop_back();                       // actually remove it
}

从区间构造 priority_queue 的操作类似：把所有元素放入 vector，然后 make_heap（O(n)）。

---

八、几段实用示例（代码片段）

1) Dijkstra（简化版）示意

using P = std::pair<int,int>; // {dist, node}
std::priority_queue<P, std::vector<P>, std::greater<P>> pq;
pq.emplace(0, start);
while(!pq.empty()){
    auto [d, u] = pq.top(); pq.pop();
    if (d != dist[u]) continue; // 忽略旧条目（惰性删除）
    // relax edges...
}

2) 求流中前 k 大元素

int k = 10;
std::priority_queue<int, std::vector<int>, std::greater<int>> minpq;
for (int x : stream) {
    if ((int)minpq.size() < k) minpq.push(x);
    else if (x > minpq.top()){
        minpq.pop();
        minpq.push(x);
    }
}
// minpq.top() 是第 k 大元素

---

总结

• 1、std::priority_queue 是对堆算法的高效封装，默认基于 vector 实现的二叉堆。它提供 top/push/pop 三个主要操作：top O(1)，push/pop O(log n)。

• 2、默认是最大堆（std::less）；要做最小堆使用 std::greater 或自定义比较器。

• 3、和 queue（FIFO）相比，priority_queue 基于优先级选择元素，适用于调度、最短路径、top-k 等问题；而 queue 适合按到达顺序处理任务（BFS、简单任务队列）。

• 4、常见注意点：比较器方向、堆非稳定、无迭代器、pop() 不返回值、对中间元素修改困难、并发需加锁。