一、什么是priority_queue
priority_queue（优先队列）是C++ STL中的一个容器，它是一个支持快速取出最大/最小元素的队列，底层使用大根堆/小根堆实现。priority_queue封装了heap的基本操作，包括push、pop、top等。priority_queue支持自定义比较器（仿函数）来实现自定义的元素比较方式。
二、基本用法
使用priority_queue需要包含头文件。priority_queue使用方法类似于普通队列，只是在创建时可以设置元素类型和比较器类型（默认使用less模板类来定义比较器，即小根堆）。
//创建int类型小根堆优先队列 priority_queue pq; //创建int类型大根堆优先队列 priority_queue<int, vector, greater> pq;
以上代码分别创建了一个int类型的小根堆和一个int类型的大根堆。在插入元素时，使用push操作在队列尾部插入一个元素。而取出队列中的最大/最小元素，可以使用top操作获取队列头部（此时是最大/最小元素）的引用，并可以使用pop操作将最大/最小元素从队列中取出。
//插入元素 pq.push(3); pq.push(1); pq.push(4); pq.push(1); //获取队列头部元素 int top_element = pq.top(); //1 //弹出队列头部元素 pq.pop();
三、自定义比较器
如果插入到priority_queue中的元素不是int类型，或者希望以一种非默认的方式进行元素比较，则可以定义自己的比较器。比较器是一个仿函数，其重载了()运算符，用于比较两个元素的大小，返回bool类型的结果。
以一个结构体为例，假设需要按照结构体中的一个整型成员变量的值从小到大排序，则可以定义比较器如下：
struct Node{
int val;
Node(int v) : val(v) {}
};
struct myComparator {
bool operator() (const Node& n1, const Node& n2) const {
return n1.val > n2.val;
}
};
priority_queue<Node, vector, myComparator> pq;
在以上示例中，定义了一个Node类型的小根堆优先队列，同时指定了比较器myComparator用于存储和取出元素时的大小判断。在myComparator中重载了()运算符，其中定义了比较规则，这里定义了n1.val > n2.val表示按照Node结构体中的val成员变量进行从小到大排序。
四、扩展应用
priority_queue还有很多其他的应用场景。例如，可以将优先队列作为一种数据结构，利用其快速取出最大/最小元素的特性解决很多问题。
例如，可以用优先队列实现topK问题，即在一堆数中找出前K大/小的数。具体实现方式是，先将前K个数插入到优先队列中，然后遍历剩下的数，如果当前数比队列头部元素小，则不做任何操作，否则将队列头部元素弹出并插入当前数。最后，队列中剩下的元素就是前K大/小的数。
//求出前K小的数
vector findKthSmallest(vector& nums, int k) {
priority_queue pq;
for (int i = 0; i < k; i++) {
pq.push(nums[i]);
}
for (int i = k; i < nums.size(); i++) {
if (nums[i] < pq.top()) {
continue;
}
pq.pop();
pq.push(nums[i]);
}
vector res;
while (!pq.empty()) {
res.push_back(pq.top());
pq.pop();
}
return res;
}
五、小结
本文重点介绍了priority_queue的用法，包括创建、插入、弹出、获取队列头部元素以及自定义比较器的实现方式。同时，还介绍了priority_queue在实际开发中的应用场景，例如用于topK问题。
原创文章，作者：小蓝，如若转载，请注明出处：https://www.506064.com/n/196138.html
微信扫一扫 
支付宝扫一扫 