C++面试不可不知的优先级队列
在C++中，优先级队列（std::priority_queue）是一个功能强大的容器适配器，它基于堆实现，提供了基于元素优先级的快速访问和排序功能。下面，我们将结合代码示例来深入理解std::priority_queue的使用方法和实战技巧。
基本用法
std::priority_queue的基本使用示例如下：
#include <iostream>
#include <queue>
int main() {
// 创建一个整型的最大堆
std::priority_queue<int> pq;
// 添加元素
pq.push(3);
pq.push(1);
pq.push(4);
// 访问顶部元素
std::cout << "Top element: " << pq.top() << std::endl; // 输出 4
// 移除顶部元素
pq.pop();
std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 3
// 检查队列是否为空
if (pq.empty()) {
std::cout << "Queue is empty." << std::endl;
}
else {
std::cout << "Queue is not empty." << std::endl;
}
// 获取队列大小
std::cout << "Size of queue: " << pq.size() << std::endl; // 输出 2
return 0;
}如上示例代码中使用了priority_queue的push、pop、top、empty、size函数，其中：
- push(const value_type& val): 在队列的尾部添加一个元素。
- pop(): 移除队列的顶部元素（即优先级最高的元素）。
- top(): 返回队列的顶部元素的引用，但不移除该元素。
- empty(): 检查队列是否为空。
- size(): 返回队列中的元素个数。
自定义比较函数
默认情况下，std::priority_queue使用std::less<T>作为比较函数实现最大堆，其也支持用户指定比较函数，如指定STL内置的比较算法，甚至自定义比较函数
使用内置比较算法
在如上的代码中，指定优先级队列的比较函数为std::greater,构建一个小顶堆，只需修改一行代码，如下：
// 创建一个整型的小顶堆
std::priority_queue<int,std::vector<int>,std::greater<int>> pq;
//其余代码同上例自定义比较函数
std::priority_queue支持自定义比较函数，示例代码如下：
#include <iostream>
#include <queue>
#include <functional>
struct Person {
std::string name;
int age;
public:
Person(const std::string& n, int a) : name(n), age(a) {}
};
// 自定义比较函数，实现最小堆
struct ComparePerson {
bool operator()(const Person& p1, const Person& p2)
{
return p1.age > p2.age;
}
};
int main() {
std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;
pq.push(Person("Alice", 25));
pq.push(Person("Bob", 20));
pq.push(Person("Charlie", 30));
std::cout << "Top element (youngest person): " \
<< pq.top().name << ", " \
<< pq.top().age << std::endl; // 输出 Charlie, 30
return 0;
}改变底层容器
默认情况下，priority_queue使用std::vector作为底层容器。但其支持在构造对象时显示指定其底层容器，如上例中在构造对象pq时指定容器为std::vector<>;也可以使用std::deque或`std::std::list作为底层容器。
//以std::queue作为底层容器
int main() {
std::priority_queue<int, std::deque<int>, std::less<int>> pq;
pq.push(3);
pq.push(1);
pq.push(4);
// 访问顶部元素
std::cout << "Top element: " << pq.top() << std::endl; // 输出 4
// 移除顶部元素
pq.pop();
std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 3
return 0;
}注意：由于priority_queue需要支持随机访问和高效的插入和删除操作，因此并不是所有的容器都适合作为底层容器。
优先级队列的遍历
在C++标准库中std::priority_queue并未直接提供遍历元素的接口，因为它是基于堆实现的，主要优化了插入和顶部元素的取出操作。所以针对优先级队列的遍历需要将值一个个取出来，示例代码如下:
int main() {
std::priority_queue<int> pq;
pq.push(20);
pq.push(15);
pq.push(30);
while (!pq.empty()) {
// 理论述逻辑上访问顶部元素，实际STL priority_queue不支持直接遍历
std::cout << pq.top() << " ";
// 正常情况下这里无法直接pop后继续遍历，因为会改变pq
// 这里仅为示意，实际代码中不能如此操作
pq.pop();
}
std::cout<<"\n";
return 0;
}
/*output：
30 20 15
*/当然将队列中所有的数据取出来放到支持迭代器的数据结构中，但是那已是对应数据结构的特性。
总结
C++的priority_queue是一个功能强大的容器适配器，它基于堆实现，提供了基于元素优先级的快速访问和排序功能。通过自定义比较函数，你可以轻松地改变priority_queue的排序方式。priority_queue虽好，但在选用数据结构要结合应用场景，慎重抉择。
腾讯云开发者
