priority_queue 容器详解

priority_queue（优先队列）是 STL 中的容器适配器，底层默认基于 vector + 堆（heap）实现，会自动将元素按优先级排序，保证堆顶元素始终是优先级最高的元素，遵循堆顶优先原则。

一、priority_queue 核心特性

1. 堆结构：底层默认是大顶堆（最大值优先），可自定义排序规则
2. 自动排序：插入元素时自动调整堆结构，保证优先级有序
3. 受限访问：只能访问 ** 堆顶（top）** 元素，不能访问其他元素
4. 高效操作：插入、删除堆顶效率为 O (log n)
5. 无迭代器：不支持遍历，无法访问非堆顶元素

二、优先队列与普通队列区别

• queue：先进先出，顺序固定，无优先级
• priority_queue：按优先级出队，与插入顺序无关
• list/vector：支持遍历 / 随机访问，优先队列不支持

三、priority_queue 基础用法

#include <iostream>
#include <queue>    // 优先队列头文件
using namespace std;

int main() {
    // 1. 默认大顶堆（最大值优先）
    priority_queue<int> pq;

    // 2. 插入元素（自动排序）
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // 3. 访问堆顶（最大值）
    cout << "堆顶元素：" << pq.top() << endl;  // 输出 50

    // 4. 删除堆顶元素
    pq.pop();
    cout << "删除后堆顶：" << pq.top() << endl; // 输出 30

    // 5. 遍历输出（只能逐个取堆顶）
    cout << "依次出队：";
    while (!pq.empty()) {
        cout << pq.top() << " ";
        pq.pop();
    }
    // 输出：30 20 10
    cout << endl;

    // 6. 常用操作
    cout << "队列大小：" << pq.size() << endl;
    cout << "是否为空：" << pq.empty() << endl;

    return 0;
}

四、priority_queue 优先队列常用操作汇总

操作	语法	说明
插入元素	push(元素)	插入元素并自动排序，效率 O(log n)
删除堆顶	pop()	删除优先级最高的堆顶元素，无返回值，效率 O(log n)
访问堆顶	top()	返回堆顶优先级最高的元素（不删除），需确保非空
判空	empty()	优先队列为空返回 true，否则返回 false
获取大小	size()	返回优先队列中元素个数

五、适用场景总结（一句话选型）

1. 需要严格先进先出的顺序 → 使用 queue
2. 广度优先搜索（BFS）→ 标准使用 queue
3. 任务排队、消息队列、缓冲处理 → 最适合 queue
4. 需要随机访问 / 中间操作 → 不要用 queue

六、注意事项

1. 不能遍历：queue 不提供迭代器，无法用 for/while 遍历全部元素
2. 访问前必须判空：调用 front () /back () /pop () 前必须确保队列非空，否则程序崩溃
3. 无 clear ()：如需清空，必须循环 pop ()
4. 底层容器：默认 deque，可手动指定 queue<int, list<int>>
5. 不可修改：只能在头尾操作，不能修改中间元素