priority_queue

std::priority_queue 是 C++ 标准库中的容器适配器，提供优先队列（最大堆）功能。它的核心特点是：插入元素后，每次从顶部取出的一定是当前队列中"优先级最高"的元素。

和普通 queue 的 FIFO 不同，priority_queue 按元素大小决定出队顺序。默认情况下，数值最大的元素优先级最高（大顶堆）。

头文件与基本特征

使用 priority_queue 时，需要包含头文件：

#include <queue>

常见特征如下：

特征	说明
类型	容器适配器，非独立容器
底层容器	默认使用 vector，也可以是 deque
排序规则	默认 std::less，大顶堆
插入	push() 后堆自动调整
删除	pop() 只删顶部，不能删中间
访问	只能访问顶部 top()，不能遍历
复杂度	push() / pop() 为 O(log n)，top() 为 O(1)

基本用法

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;

    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    while (!pq.empty()) {
        std::cout << pq.top() << ' ';
        pq.pop();
    }
    // 输出：50 30 20 10

    return 0;
}

默认大顶堆，最大元素在顶部。每次 pop() 都会移除当前最大元素，然后堆自动下沉调整。

常用成员函数

函数	作用
push(x)	插入元素
pop()	移除顶部元素
top()	返回顶部元素引用
empty()	判断是否为空
size()	返回元素个数

注意：priority_queue 不提供迭代器，也不能通过下标访问中间元素。

小顶堆：自定义比较器

默认 std::less 产生大顶堆。如果要小顶堆（最小值在顶部），可以用 std::greater：

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int> > pq;

    pq.push(30);
    pq.push(10);
    pq.push(50);

    while (!pq.empty()) {
        std::cout << pq.top() << ' ';
        pq.pop();
    }
    // 输出：10 30 50

    return 0;
}

这里三个模板参数分别是：元素类型、底层容器类型、比较器类型。如果要自定义比较器，第二个参数（底层容器）也必须显式写出。

自定义类型与比较器

当元素是自定义类型时，可以通过重载 operator< 或传入比较器来定义优先级：

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

struct Task {
    std::string name;
    int priority;
};

struct CompareTask {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority;  // priority 越高越先出队
    }
};

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

    Task t1;
    t1.name = "write docs";
    t1.priority = 3;
    pq.push(t1);

    Task t2;
    t2.name = "fix bug";
    t2.priority = 10;
    pq.push(t2);

    Task t3;
    t3.name = "reply email";
    t3.priority = 1;
    pq.push(t3);

    while (!pq.empty()) {
        std::cout << pq.top().name << " (" << pq.top().priority << ")\n";
        pq.pop();
    }
    // 按 priority 从高到低输出

    return 0;
}

比较器必须满足严格弱序关系。

典型场景

1. 任务调度：按优先级处理任务，优先级高的先执行。
2. Top-K 问题：维护一个固定大小的小顶堆来找最大的 K 个元素。
3. Dijkstra 最短路径：每次选择当前距离最小的未处理节点。
4. 哈夫曼编码：每次取出两个最小频率的节点合并。
5. 合并有序流：将多个有序输入流归并为一个有序输出。

Top-K 示例（用小顶堆找最大的 3 个）：

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

int main() {
    std::vector<int> nums;
    nums.push_back(7);
    nums.push_back(2);
    nums.push_back(9);
    nums.push_back(1);
    nums.push_back(5);
    nums.push_back(3);

    const int k = 3;
    std::priority_queue<int, std::vector<int>, std::greater<int> > minHeap;

    for (std::vector<int>::size_type i = 0; i < nums.size(); ++i) {
        minHeap.push(nums[i]);
        if (minHeap.size() > static_cast<std::size_t>(k)) {
            minHeap.pop();
        }
    }

    while (!minHeap.empty()) {
        std::cout << minHeap.top() << ' ';
        minHeap.pop();
    }
    // 输出：7 5 9 （最大的三个，顺序取决于堆排列）

    return 0;
}

使用注意

1. priority_queue 没有迭代器，不能遍历或查找中间元素。
2. 如果只需要先进先出，使用普通 queue；需要两端操作，使用 deque。
3. 自定义比较器时，第三个模板参数是比较器的类型，不是实例。
4. 小顶堆用 greater 时，三个模板参数必须全写。
5. pop() 返回 void，要获取顶部元素先 top() 再 pop()。

小结

std::priority_queue 是堆数据结构的高层封装，适合"每次取最值"的场景。默认大顶堆、O(log n) 的插入和删除，配合自定义比较器可以灵活控制优先级逻辑。它的接口虽然简单，但在算法题和工程调度中都非常常用。