priority_queue：优先队列的实战心法

优先队列这个东西，说白了就是一个会自动排序的队列。你往里扔数据，它自己就按优先级排好队。我刚开始学STL时觉得这玩意儿不就是个排序吗？后来在项目中用多了才发现，它解决的是「动态取最值」的问题，跟普通排序完全是两码事。

优先队列的核心概念

普通队列是先进先出，像排队买奶茶。优先队列不一样——谁优先级高谁先出。这个优先级你可以自己定义，默认是数值大的优先。

底层实现是堆（heap），通常是二叉堆。所以插入和删除的时间复杂度都是O(log n)，取顶是O(1)。嗯，这个效率在大多数场景下够用了。

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
    
    while (!pq.empty()) {
        std::cout << pq.top() << " ";
        pq.pop();
    }
    // 输出: 30 20 10 5
    
    return 0;
}

输出顺序是从大到小。为什么？因为默认用的是 std::less<T> 作为比较器，但优先队列的规则是：比较器返回 true 时，元素优先级更低。所以 less 反而让大的元素在堆顶。

自定义优先级

实际项目中，很少直接用int。更多时候是自定义类型。比如任务调度：

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

struct Task {
    std::string name;
    int priority;    // 数值越大越紧急
    int duration;    // 执行时长
    
    Task(const std::string& n, int p, int d)
        : name(n), priority(p), duration(d) {}
};

// 自定义比较器
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        // 优先级高的先执行
        // 优先级相同，时长短的先执行
        if (a.priority != b.priority)
            return a.priority < b.priority;  // 注意：返回true表示a优先级更低
        return a.duration > b.duration;
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;
    
    taskQueue.push(Task("登录模块", 5, 10));
    taskQueue.push(Task("支付接口", 10, 30));
    taskQueue.push(Task("日志写入", 3, 5));
    taskQueue.push(Task("数据备份", 10, 15));
    
    while (!taskQueue.empty()) {
        Task t = taskQueue.top();
        taskQueue.pop();
        std::cout << "执行: " << t.name 
                  << " (优先级:" << t.priority 
                  << ", 耗时:" << t.duration << ")" << std::endl;
    }
    
    return 0;
}

输出结果：

执行: 支付接口 (优先级:10, 耗时:30)
执行: 数据备份 (优先级:10, 耗时:15)
执行: 登录模块 (优先级:5, 耗时:10)
执行: 日志写入 (优先级:3, 耗时:5)

注意比较器的写法。很多人在这里栽跟头——operator() 返回 true 表示第一个参数的优先级低于第二个。说白了就是：你想让 a 排在 b 后面，就返回 true。

小顶堆的实现

想要最小值优先？用 std::greater<T>：

// 小顶堆：最小值优先
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

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

// 输出: 5 10 20 30
while (!minHeap.empty()) {
    std::cout << minHeap.top() << " ";
    minHeap.pop();
}

实际应用场景

优先队列在真实项目中用得非常多。我挑几个典型的说说：

• 任务调度系统：操作系统里的进程调度，紧急任务优先执行
• Dijkstra最短路径：每次从优先队列中取出当前距离最小的节点
• 合并K个有序链表：把每个链表的头节点放入优先队列，每次取最小的
• Top K问题：维护一个大小为K的小顶堆，遍历数据时不断替换堆顶
• 事件驱动模拟：按时间戳排序的事件队列

拿Top K问题举个例子。比如从100万个数字中找出最大的10个：

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

std::vector<int> findTopK(const std::vector<int>& data, int k) {
    // 小顶堆，堆顶是最小值
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    for (int num : data) {
        if (minHeap.size() < k) {
            minHeap.push(num);
        } else if (num > minHeap.top()) {
            minHeap.pop();
            minHeap.push(num);
        }
    }
    
    std::vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top());
        minHeap.pop();
    }
    // 结果是从小到大，可以反转一下
    std::reverse(result.begin(), result.end());
    return result;
}

int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9};
    auto top5 = findTopK(data, 5);
    
    std::cout << "最大的5个数: ";
    for (int x : top5) std::cout << x << " ";
    // 输出: 9 9 9 8 7
    
    return 0;
}

这个算法的时间复杂度是O(n log k)，空间复杂度O(k)。如果k远小于n，比全排序高效得多。

知识体系总览

下面这张图帮你理清优先队列的核心脉络：

避坑指南

最后总结几个我踩过的坑：

1. 比较器方向：记住，operator()(a, b) 返回 true 表示 a 排在 b 后面。写完后用几个简单数据验证一下。
2. 空队列访问 top()：这是未定义行为，程序可能直接崩溃。每次调用 top() 前检查 empty()。
3. 元素拷贝开销：如果存储的是大对象，优先队列内部会频繁拷贝。建议存指针或智能指针。
4. 迭代器失效：priority_queue 不提供迭代器，别想着遍历。真想遍历就先把元素拷出来。

优先队列是个好东西，用对了地方能省不少事。但记住它的定位——它只解决「动态取最值」这一个问题。别拿它当万能排序工具使。

---

公众号:蓝海资料掘金营，微信deep3321