这里先简单介绍一下优先级队列priority_queue： 优先队列是一种容器适配器,默认的情况下，如果没有为特定的priority_queue类实例化指容器类，则使用vector (deque 也是可以的),需要支持随机访问迭代器，以便始终在内部保持堆结构
文章目录
*
– 一、使用
– 二、仿函数
– 三、模拟实现
–
+ 1、基础接口
+ 2、push与向上调整
+ 3、pop与向下调整
+ 4、构造函数
+ 5、总体代码
一、使用
在有了前面容器使用的基础之下，我们对于优先级队列priority_queue的使用成本不是很大，值得注意的是头文件为
普通的队列是先进先出，优先级队列默认是优先级高的先出
Container:优先级队列默认使用vector作为其底层存储数据的容器，支持[]的使用，支持随机访问，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
Compare:注意：默认情况下priority_queue是大堆，仿函数为less。
构造函数
接口
查看文档的接口
常用接口
函数声明接口说明priority_queue()/priority_queue(first, last)构造一个空的优先级队列empty( )检测优先级队列是否为空，是返回true，否则返回 falsetop( )返回优先级队列中最大(最小元素)，即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素，即堆顶元素
直接进入代码环节：
1.默认情况下，priority_queue是大堆
2.想让priority_queue是小堆:greater,头文件为functional
到了这里，我们发现priority_queue的使用并不难，下面，我们通过一道题目来看看priority_queue的妙处把：
- 数组中的第K个最大元素
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
直接排序是O（NlogN），这个地方既可以建大堆也可以建小堆:建n个数的大堆，建堆是O(n),然后在pop K次，即O（N+klogN），缺陷在于N太大。建K个数的小堆，剩下的数进一个数据与堆顶做比较，大的进堆，最终第K大的就是堆顶，建K个数的小堆为O（K），故时间复杂度为O（K+（N-K）logK），当N远大于K是建议采用第二种。
第一种：建n个数的大堆
class Solution {
public:
int findKthLargest(vector& nums, int k) {
//建大堆
priority_queue pq(nums.begin(),nums.end());
//前k-1个pop
while(--k)
{
pq.pop();
}
return pq.top();
}
};
第二种：建K个数的小堆
class Solution {
public:
int findKthLargest(vector& nums, int k) {
//前k个数建小堆
priority_queue,greater>pq(nums.begin(),nums.begin()+k);
for(size_t i =k;ipq.top())
{
pq.pop();
pq.push(nums[i]);
}
}
return pq.top();
}
};
我们可以发现在有了优先级队列之后我们对于这道题的解法大大简便了。不用像之前一样去自己手动实现一个堆了。
二、仿函数
仿函数/函数对象也是类，是一个类对象。仿函数要重载operator()，我们直接自己来通过代码来看一看仿函数：
namespace hwc
{
template
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template
class greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
}
int main()
{
hwc::less lessFunc;
lessFunc(1, 2);
return 0;
}
//lessFunc是一个对象，仿函数对象，可以像函数一样使用
仿函数的作用在于：在C语言中我们通过传入函数指针解决升序降序问题，虽然C++兼容了C，但是C++并没有继续利用函数指针，而是通过仿函数来控制升序和降序，我们直接以之前写过的排序为例子，通过利用仿函数来实现升序和降序：
template
void BubbleSort(T* a, int n, Compare com)
{
for (int j = 0; j < n; j++)
{
int exchange = 0;
for (int i = 1; i < n - j; i++)
{
//if (a[i] lessFunc;
hwc::greater greaterFunc;
lessFunc(1, 2);
int a[] = { 2,3,4,5,6,1,2,8 };
BubbleSort(a, sizeof(a) / sizeof(int),lessFunc);
for (auto e : a)
{
cout << e << " ";
}
cout << endl;
BubbleSort(a, sizeof(a) / sizeof(int), greaterFunc);
for (auto e : a)
{
cout << e << " ";
}
cout << endl;
return 0;
}
传值传参问题：这里是直接传值传参Compare com,当然也可以传引用传参const Compare& com,不过要记得加上const进行修饰，另外一般的仿函数比较小，问题不是很大。
自定义类型
这里的比较大小是比较常见的，如果是自定义类型：
比如日期类，那该如何去进行大小的比较？一种是重载大小的比较运算符，使之支持日期类的大小比较。另一种是可以自己定义仿函数专门去进行日期类的大小比较
1.重载运算符
比较大小需要我们自己去重载>,
Original: https://blog.csdn.net/weixin_60478154/article/details/128603118
Author: 平凡的人1
Title: 【C++】优先级队列priority_queue&&仿函数
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/813307/
转载文章受原作者版权保护。转载请注明原作者出处！