14. std::priority_queue 详解：优先队列的实现（堆）、自定义比较器、应用场景（Top-K 问题）

说到优先队列，我脑子里第一个蹦出来的场景就是：几年前做实时行情系统时，需要从每秒涌入的几万笔交易中，快速找出价格最高的前10笔。用普通数组排序？那性能直接崩了。用 std::priority_queue？嗯，几行代码搞定。

说白了，priority_queue 就是一个「谁优先级高谁先出」的队列。它底层用的是堆（heap），默认是大顶堆——也就是最大的元素永远在队首。

14.1 优先队列的本质：堆

你可能会问：为什么优先队列要用堆？我直接排序不行吗？

想想看，排序的时间复杂度是 O(n log n)，而堆的插入和删除都是 O(log n)。如果你需要频繁地插入和取出最大/最小元素，堆的优势就非常明显了。我在项目中处理流式数据时，几乎只用堆，不用排序。

std::priority_queue 默认使用 std::vector 作为底层容器，配合 std::make_heap、std::push_heap、std::pop_heap 这些算法。你不需要手动调用这些函数，优先队列已经帮你封装好了。

14.2 基本用法：从入门到上手

先看一个最简单的例子：

#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(); // 移除 30
    std::cout << "新的队首: " << pq.top() << std::endl; // 输出 20

    return 0;
}

输出结果：

队首元素: 30
新的队首: 20

嗯，这里要注意：priority_queue 没有 begin() 和 end()，你不能遍历它。只能通过 top() 看队首，通过 push() 和 pop() 操作。这是适配器的典型特征——只暴露最核心的接口。

14.3 自定义比较器：小顶堆与复杂类型

默认是大顶堆，那怎么变成小顶堆？很简单，用 std::greater<T>：

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // for std::greater

int main() {
    // 小顶堆：最小的元素在队首
    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

    return 0;
}

模板参数有三个：元素类型、底层容器类型、比较器类型。很多人只写前两个，忘了第三个，结果编译报错。我刚开始学的时候也踩过这个坑。

如果是自定义类型呢？比如一个 Task 结构体，按优先级排序：

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

struct Task {
    int id;
    int priority;
    std::string description;
};

// 自定义比较器：优先级高的先出
struct CompareTask {
    bool operator()(const Task& a, const Task& b) {
        return a.priority < b.priority; // 大顶堆：priority 大的在队首
    }
};

int main() {
    std::priority_queue<Task, std::vector<Task>, CompareTask> task_queue;

    task_queue.push({1, 5, "低优先级任务"});
    task_queue.push({2, 10, "高优先级任务"});
    task_queue.push({3, 7, "中优先级任务"});

    std::cout << "队首任务ID: " << task_queue.top().id << std::endl; // 输出 2

    return 0;
}

14.4 避坑指南：我踩过的三个坑

坑一：比较器方向搞反

我曾经在写 Top-K 问题时，想找最小的 K 个数，结果用了默认的大顶堆，取出来的全是最大的。记住：std::greater<T> 才是小顶堆。

坑二：忘记包含头文件

std::greater 在 <functional> 里，不是 <queue>。我有一回在 Linux 下编译，报了一堆模板错误，找了半天才发现是头文件没包含。

坑三：自定义类型没有定义 operator<

如果你不想写仿函数，也可以直接在结构体里重载 operator<。但注意：默认是大顶堆，所以 operator< 返回 true 表示当前对象优先级更低。这个逻辑有点绕，我建议还是用仿函数，更直观。

14.5 应用场景：Top-K 问题

Top-K 是面试高频题，也是实际项目中的常客。比如：从海量日志中找出出现次数最多的 K 个 IP，或者从商品列表中找出价格最高的 K 个商品。

思路很简单：维护一个大小为 K 的小顶堆。遍历数据时，如果堆未满，直接插入；如果堆已满，且当前元素比堆顶大，则弹出堆顶，插入当前元素。这样遍历结束后，堆里就是最大的 K 个元素。

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

std::vector<int> findTopK(const std::vector<int>& data, int k) {
    if (k <= 0) return {};

    // 小顶堆：堆顶是最小的，方便淘汰
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    for (int num : data) {
        if (min_heap.size() < k) {
            min_heap.push(num);
        } else if (num > min_heap.top()) {
            min_heap.pop();
            min_heap.push(num);
        }
    }

    // 把堆里的元素取出来
    std::vector<int> result;
    while (!min_heap.empty()) {
        result.push_back(min_heap.top());
        min_heap.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};
    int k = 3;
    auto top_k = findTopK(data, k);

    std::cout << "最大的 " << k << " 个数: ";
    for (int x : top_k) {
        std::cout << x << " ";
    }
    std::cout << std::endl; // 输出 9 6 5

    return 0;
}

时间复杂度是 O(n log k)，空间复杂度是 O(k)。如果 k 远小于 n，这个方案非常高效。

14.6 知识体系图

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

14.7 小结

优先队列是个小而美的工具。它不复杂，但用好了能解决很多实际问题。我个人觉得，掌握它最好的方式就是动手写一个 Top-K 的 demo，然后试着改一改比较器，看看行为怎么变。

记住三个关键点：底层是堆、默认是大顶堆、自定义比较器用仿函数。下次面试或者写代码时，你就能自信地说：「这个用优先队列，几行搞定。」

---

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