STL-优先级队列使用总结

优先队列（priority_queue）是 C++ STL 中的一种容器适配器，用于存储具有优先级的元素。以下是 priority_queue 的常见用法：

1. 包含头文件

#include <queue>

2. 声明和初始化

默认情况下，priority_queue 是一个最大堆，优先级最高的元素在队首。

std::priority_queue<int> pq; // 默认最大堆

3. 插入元素

使用 push 方法添加元素：

pq.push(10);
pq.push(5);
pq.push(20);

4. 访问最高优先级元素

使用 top 方法获取优先级最高的元素，但不删除它：

int topElement = pq.top(); // 返回 20

5. 删除最高优先级元素

使用 pop 方法删除优先级最高的元素：

pq.pop(); // 删除 20

6. 检查队列大小

可以使用 size 方法获取当前元素个数：

size_t size = pq.size(); // 获取当前元素数量

7. 检查队列是否为空

使用 empty 方法检查队列是否为空：

if (pq.empty()) {// 队列为空
}

8. 自定义比较器

可以通过传入自定义比较器实现最小堆或其他优先级规则：

struct Compare {bool operator()(int a, int b) {return a > b; // 最小堆}
};std::priority_queue<int, std::vector<int>, Compare> minHeap;

9. 示例代码

#include <iostream>
#include <queue>
#include <vector>int main() {std::priority_queue<int> pq;pq.push(10);pq.push(5);pq.push(20);std::cout << "Top element: " << pq.top() << std::endl; // 20pq.pop();std::cout << "Next top element: " << pq.top() << std::endl; // 10return 0;
}

---

优先队列常用于需要处理具有优先级的任务或元素的场景，如调度算法、任务管理等。

在 C++ STL 的优先队列实现中，比较器的定义和使用方式决定了元素的优先级顺序。具体来说，当比较器返回 true 时，表示第一个参数的优先级低于第二个参数。这是通过以下机制实现的：

1. 优先队列的内部实现

优先队列通常基于堆（heap）数据结构实现。堆是一种特殊的完全二叉树，具有以下特性：

• 大顶堆：父节点的值大于或等于其子节点的值。这样，根节点总是最大的元素。
• 小顶堆：父节点的值小于或等于其子节点的值。这样，根节点总是最小的元素。

2. 比较器的作用

比较器通过 operator() 函数返回一个布尔值来决定元素的相对优先级：

• return a < b：表示 a 的优先级低于 b。
  • 在插入新元素时，如果要保持堆的性质，优先队列会将 b 排在 a 之前。这意味着 b 应该在队列中更靠前（优先被提取）。

3. 示例解释

假设你有以下元素：

• 插入 10 和 20。

当调用 push(10) 和 push(20) 时：

• 在插入 20 时，比较 10 和 20：
  • 调用比较器 operator()(10, 20)，返回 true（因为 10 < 20）。
  • 因此，优先队列将安排 20 在 10 之前，因为 20 更大，优先级更高。

4. 优先队列的行为

• 当你调用 top() 时，总是会返回优先级最高的元素（在大顶堆中为最大元素）。
• 因此，优先队列的行为是确保较大元素（在此例中为 20）在队列的前面。

总结

比较器的定义通过返回值直接影响元素在优先队列中的排列顺序。当比较器返回 true 时，表示第一个元素的优先级较低，优先队列会相应地调整元素顺序，以保持堆的特性，从而确保提取时总是获得优先级最高的元素。