C++之priority_queue容器

priority_queue 是 C++ STL (Standard Template Library) 中的一种容器适配器，用于实现优先队列。优先队列是一种特殊的队列，其中每个元素都有一个优先级，元素的出队顺序取决于其优先级，而不是插入顺序。默认情况下，优先队列是一个最大堆，即优先级最高的元素（通常是最大的元素）会被首先处理。

主要特点

1. 优先级：每个元素都有一个优先级，出队顺序取决于优先级。
2. 最大堆：默认情况下，优先队列是一个最大堆，优先级最高的元素（最大的元素）会被首先处理。
3. 基本操作：提供 push、pop、top、empty 和 size 等基本操作。
4. 容器适配器：priority_queue 是一个容器适配器，可以基于不同的底层容器实现，默认情况下使用 vector。

常用操作

定义和初始化

#include <queue>std::priority_queue<int> pq; // 创建一个空的 priority_queue 容器，默认为最大堆
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq; // 创建一个最小堆的 priority_queue

插入元素

pq.push(1); // 插入元素 1
pq.push(3); // 插入元素 3
pq.push(2); // 插入元素 2

移除元素

pq.pop(); // 移除优先级最高的元素

访问优先级最高的元素

if (!pq.empty()) {std::cout << "Top element: " << pq.top() << std::endl; // 访问优先级最高的元素
} else {std::cout << "Priority queue is empty." << std::endl;
}

检查优先队列是否为空

if (pq.empty()) {std::cout << "Priority queue is empty." << std::endl;
} else {std::cout << "Priority queue is not empty." << std::endl;
}

获取优先队列的大小

std::cout << "Priority queue size: " << pq.size() << std::endl;

示例代码

以下是一个完整的示例，展示了如何使用 priority_queue：

#include <iostream>
#include <queue>int main() {std::priority_queue<int> pq; // 创建一个最大堆的 priority_queue// 插入元素pq.push(1);pq.push(3);pq.push(2);// 输出优先级最高的元素while (!pq.empty()) {std::cout << "Top element: " << pq.top() << std::endl;pq.pop();}// 创建一个最小堆的 priority_queuestd::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;// 插入元素min_pq.push(1);min_pq.push(3);min_pq.push(2);// 输出优先级最高的元素while (!min_pq.empty()) {std::cout << "Top element (min heap): " << min_pq.top() << std::endl;min_pq.pop();}return 0;
}

自定义比较函数

如果你需要自定义优先级的计算方式，可以提供一个自定义的比较函数或对象。例如，假设你有一个自定义的结构体：

#include <queue>
#include <string>struct Person {std::string name;int age;bool operator<(const Person& other) const {return age < other.age; // 按年龄从小到大排序}
};int main() {std::priority_queue<Person> pq;// 插入元素pq.push({"Alice", 30});pq.push({"Bob", 25});pq.push({"Charlie", 35});// 输出优先级最高的元素while (!pq.empty()) {std::cout << "Top element: " << pq.top().name << ", " << pq.top().age << std::endl;pq.pop();}return 0;
}

总结

priority_queue 是一个非常有用的数据结构，适用于需要根据优先级处理元素的场景。常见的应用场景包括任务调度、事件处理、Dijkstra 最短路径算法等。由于 priority_queue 是一个容器适配器，你可以选择不同的底层容器来实现它，以适应不同的性能需求。默认情况下，priority_queue 使用 vector 作为底层容器，因为它在大多数情况下提供了良好的性能。