C++优先队列详解（从零开始掌握priority_queue的使用与实现）

什么是优先队列？

优先队列是一种特殊的队列，其中每个元素都有一个“优先级”。出队时，并不是按照先进先出（FIFO）原则，而是优先级最高的元素先出队。

在C++标准模板库（STL）中，std::priority_queue 就是优先队列的实现。它底层通常基于堆（Heap）数据结构，支持快速插入和删除最大（或最小）元素。

C++优先队列的基本用法

要使用 priority_queue，需要包含头文件 <queue>。

1. 默认最大堆（最大值优先）

#include <iostream>#include <queue>int main() {    std::priority_queue<int> pq; // 默认是最大堆    pq.push(10);    pq.push(30);    pq.push(20);    while (!pq.empty()) {        std::cout << pq.top() << " "; // 输出顶部元素        pq.pop(); // 弹出顶部元素    }    // 输出：30 20 10    return 0;}

注意：top() 返回最高优先级元素，pop() 删除该元素。

2. 最小堆（最小值优先）

如果希望最小的元素优先出队，可以使用 std::greater<T> 作为比较器：

#include <iostream>#include <queue>#include <functional> // for std::greaterint main() {    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;    pq.push(10);    pq.push(30);    pq.push(20);    while (!pq.empty()) {        std::cout << pq.top() << " ";        pq.pop();    }    // 输出：10 20 30    return 0;}

自定义类型的优先队列

当我们处理自定义结构体（如任务、学生等）时，需要定义比较规则。有三种方式：

方法一：重载 < 运算符

#include <iostream>#include <queue>struct Student {    std::string name;    int score;    // 重载 < 运算符：分数高的优先级高    bool operator<(const Student& other) const {        return score < other.score;    }};int main() {    std::priority_queue<Student> pq;    pq.push({"Alice", 95});    pq.push({"Bob", 88});    pq.push({"Charlie", 92});    while (!pq.empty()) {        std::cout << pq.top().name << ": " << pq.top().score << std::endl;        pq.pop();    }    // 输出：    // Alice: 95    // Charlie: 92    // Bob: 88    return 0;}

方法二：使用函数对象（Functor）

struct CompareStudent {    bool operator()(const Student& a, const Student& b) {        return a.score < b.score; // 注意：priority_queue是最大堆，所以这里 < 表示高分优先    }};// 使用方式：std::priority_queue<Student, std::vector<Student>, CompareStudent> pq;

STL优先队列教程：常见操作总结

C++堆结构与性能分析

C++中的 priority_queue 底层默认使用 std::vector 作为容器，并通过堆算法维护堆性质。堆是一种完全二叉树，分为最大堆和最小堆：

• 最大堆：父节点 ≥ 子节点 → 根节点是最大值
• 最小堆：父节点 ≤ 子节点 → 根节点是最小值

正因为这种结构，插入和删除操作都能在 O(log n) 时间内完成，非常适合需要频繁获取最值的场景。

结语

通过本篇STL优先队列教程，你应该已经掌握了 priority_queue 的基本用法、自定义类型处理以及底层C++堆结构的工作原理。无论你是准备面试还是开发实际项目，C++优先队列都是你不可或缺的工具。

赶快动手写几个例子试试吧！记住：实践是掌握编程的最佳方式。