C++ 容器类 <priority_queue>（完整指南）

C++ 容器类 <priority_queue> 入门与实战指南

在 C++ 的标准模板库（STL）中，priority_queue 是一个非常实用且高效的容器类，它实现了“优先队列”这种数据结构。如果你曾经在医院挂号时看到“急诊优先”、“重症优先”的标识，那其实就是一种“优先级队列”的现实映射。在程序中，我们常常需要按照某种规则对元素进行排序，比如任务调度、Dijkstra 最短路径算法、合并 K 个有序链表等场景，priority_queue 就是解决这类问题的利器。

与 vector 或 list 不同，priority_queue 并不保证元素的插入顺序，而是始终保证“队首元素”是当前优先级最高的那个。它底层通常基于堆（heap）实现，因此插入和取出操作的时间复杂度均为 O(log n)，效率极高。

什么是优先队列？—— 从生活场景说起

想象一下你在处理多个任务，比如写代码、回复邮件、开会、吃饭。你不可能按“谁先来谁先做”的方式处理，而是会优先处理紧急或重要的任务。这就是“优先队列”的核心思想：不是先来后到，而是按优先级决定处理顺序。

在 C++ 中，priority_queue 就是这种逻辑的代码实现。它允许你将元素插入队列，然后自动根据预设的规则（默认是大顶堆）把优先级最高的元素放到队首，供你随时取出。

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

int main() {
    // 创建一个优先队列，存储整数
    std::priority_queue<int> pq;

    // 插入元素
    pq.push(10);
    pq.push(30);
    pq.push(20);
    pq.push(5);

    // 由于默认是大顶堆，队首是最大的元素
    std::cout << "队首元素: " << pq.top() << std::endl;  // 输出 30

    // 弹出队首元素
    pq.pop();

    std::cout << "弹出后队首: " << pq.top() << std::endl;  // 输出 20

    return 0;
}

注释：std::priority_queue<int> 默认使用 std::less<int> 作为比较函数，构建的是大顶堆，即队首是当前最大值。top() 用于查看队首元素但不移除，pop() 用于移除队首元素。

默认行为：大顶堆的底层机制

priority_queue 默认使用 std::vector 作为底层容器，并通过 std::less 比较函数构建最大堆。这意味着队列中最大元素永远在顶部。

但你可能会想：“如果我想实现最小堆怎么办？”——这正是 priority_queue 灵活之处。我们可以通过模板参数自定义比较逻辑。

#include <iostream>
#include <queue>
#include <functional>  // 提供 std::greater

int main() {
    // 使用 std::greater 构建最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

    min_pq.push(10);
    min_pq.push(30);
    min_pq.push(20);
    min_pq.push(5);

    std::cout << "最小堆队首: " << min_pq.top() << std::endl;  // 输出 5

    min_pq.pop();
    std::cout << "弹出后队首: " << min_pq.top() << std::endl;  // 输出 10

    return 0;
}

注释：std::priority_queue<int, std::vector<int>, std::greater<int>> 中的三个模板参数分别表示：

• int：存储的数据类型
• std::vector<int>：底层容器（可选，通常默认）
• std::greater<int>：比较函数对象，实现最小堆

自定义比较逻辑：让优先级由你定义

在实际开发中，我们处理的往往是复杂类型，比如 struct Task 或 class Student。这时，仅用数字作为优先级显然不够。我们可以定义自己的比较函数，甚至使用 Lambda 表达式。

比如，假设我们有一个任务队列，每个任务有“名称”和“优先级值”，我们希望按优先级值从高到低排序。

#include <iostream>
#include <queue>
#include <string>
#include <functional>

// 定义任务结构体
struct Task {
    std::string name;
    int priority;

    // 构造函数
    Task(const std::string& n, int p) : name(n), priority(p) {}
};

// 自定义比较函数对象（大顶堆）
struct CompareTask {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority;  // 注意：这里是小于号
    }
};

int main() {
    // 使用自定义比较函数创建优先队列
    std::priority_queue<Task, std::vector<Task>, CompareTask> task_pq;

    task_pq.push(Task("登录验证", 8));
    task_pq.push(Task("数据备份", 3));
    task_pq.push(Task("日志清理", 10));
    task_pq.push(Task("邮件发送", 5));

    // 依次取出任务，按优先级从高到低
    while (!task_pq.empty()) {
        Task t = task_pq.top();
        std::cout << "执行任务: " << t.name 
                  << " (优先级: " << t.priority << ")" << std::endl;
        task_pq.pop();
    }

    return 0;
}

注释：CompareTask 中的 operator() 返回 true 表示 a 应该排在 b 后面。由于 priority_queue 是最大堆，当 a.priority < b.priority 时，a 会被排在 b 后面，从而实现“高优先级任务先处理”。

常见操作与实用技巧

priority_queue 提供了几个关键接口，掌握它们能让你在项目中游刃有余。

注释：top() 和 pop() 都不能在空队列上调用，否则会引发未定义行为。建议在调用前使用 empty() 判断。

实际案例：合并 K 个有序链表

这是一个经典的面试题，也是 priority_queue 的典型应用场景。我们用 priority_queue 维护每个链表的当前头节点，每次取出最小值，然后将该节点的下一个节点加入队列。

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

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 比较函数，用于最小堆
struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val;  // 小的在前
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    // 创建最小堆
    std::priority_queue<ListNode*, std::vector<ListNode*>, Compare> pq;

    // 将每个链表的头节点加入堆
    for (auto list : lists) {
        if (list) {
            pq.push(list);
        }
    }

    ListNode dummy(0);  // 虚拟头节点
    ListNode* current = &dummy;

    // 从堆中取出最小元素，连接到结果链表
    while (!pq.empty()) {
        ListNode* node = pq.top();
        pq.pop();

        current->next = node;
        current = current->next;

        // 如果该节点还有下一个节点，加入堆
        if (node->next) {
            pq.push(node->next);
        }
    }

    return dummy.next;
}

注释：此算法时间复杂度为 O(N log K)，其中 N 是所有节点总数，K 是链表数量。priority_queue 在这里起到了“动态选择最小头节点”的作用，是整个算法的核心。

常见误区与注意事项

1. 不要直接修改 priority_queue 中的元素值
   一旦元素进入队列，其位置由堆结构决定，直接修改值会导致堆结构破坏。如果需要更新，应先 pop()，修改后再 push()。

2. 注意比较函数的逻辑方向
   priority_queue 默认是大顶堆，若想实现最小堆，必须使用 std::greater 或自定义比较函数，且逻辑要反向。

3. 避免在循环中频繁 push/pop 大量数据
   虽然 priority_queue 的操作是 O(log n)，但频繁调用仍会影响性能。如有需要，可考虑使用 std::vector + std::make_heap 手动管理堆。

4. 不要在空队列上调用 top() 或 pop()
   这是常见错误，务必在操作前检查 empty()。

总结：掌握 C++ 容器类 <priority_queue> 的关键

priority_queue 是 C++ 中不可或缺的容器类，尤其适合处理“按优先级处理元素”的问题。它不仅高效，而且灵活，通过自定义比较函数，可以轻松应对各种复杂场景。

从简单的整数排序，到复杂的任务调度、图算法实现，priority_queue 都能大显身手。理解它的底层机制（堆结构）、掌握其核心接口，并结合实际案例练习，是每个 C++ 开发者进阶的必经之路。

无论你是初学者还是中级开发者，熟练使用 priority_queue 都能显著提升你的算法设计能力。在刷题、写系统模块、优化性能时，它都可能成为你的“隐藏武器”。

记住：不是所有队列都按顺序来，有时，最高优先级的那个，才是最先被处理的。