priority_queue介绍
1.优先级队列是一种容器适配器，根据弱排序标准，它的第一个元素总是最大的
2.此上下文类似于堆，堆中可以随时插入元素，检索最大堆元素
3.优先队列实现为容器适配器，容器适配器即将特定容器类封装作为底层容器类，queue提供一组特定的成员函数访问其元素，元素从特定容器的“尾部”弹出，称为优先级队列的顶部
4.底层容器可以是任何标准容器类的模板，也可以是特定设计的容器类，容器应该可以通过随机访问迭代器访问，并支持以下操作：
- empty (): 检测是否为空
- size ():返回有效元素个数
- top (): 返回第一个元素的引用
- push_back (): 在容器尾部插入元素
- pop_back (): 删除容器尾部元素
5.标准容器类vector和deque满足这些要求,如果没有初始化容器,默认使用vector
6.需要支持随机访问迭代器，以便始终保持内部结构，容器适配器需要时自动调用算法函数make_heap, push_heap 和 pop_heap完成操作
使用
| 函数声明 | 接口说明 |
|---|---|
| priority ()/priotirt queue (first, last) | 构造一个空队列 |
| empty () | 检测是否为空 |
| top () | 返回队列中堆顶的元素 |
| push () | 插入元素 |
| pop () | 删除堆顶元素 |
默认情况下是大堆
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
// 默认情况下，创建的是大堆，其底层按照小于号比较
vector<int> v{3,2,7,6,0,4,1,9,8,5};
priority_queue<int> q1;
for (auto& e : v)
q1.push(e);
cout << q1.top() << endl;
// 如果要创建小堆，将第三个模板参数换成greater比较方式
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
cout << q2.top() << endl;
}
练习
数组第k大元素
解析
将数组排序返回倒数第k个就可以完成，但时间复杂度不够。可以用优先级队列，将数组里的元素插入队列，弹k-1次队列，堆顶就是第k大的元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> que;
for (auto ch : nums) {
que.push(ch);
}
while (--k) {
que.pop();
}
return que.top();
}
};
这种解法时间复杂度是O(k*logN + N)，如果N远大于k，复杂度也会变高，可以优化一下，只用前k个元素建堆，比较数组剩下元素，更大的进堆，这样空间和效率都会好很多
先建立一个小堆的优先队列，前k个元素。从数组第k个元素开始遍历，比堆顶大就替换进去，先出堆顶再入堆。这样堆里就是整个数组前k大的元素，第k大的就是堆顶的元素
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> que(nums.begin(),
nums.begin() + k);
for (int i = k; i < nums.size(); i++) {
if (nums[i] > que.top()) {
que.pop();
que.push(nums[i]);
}
}
return que.top();
}
};
实现
既然是容器适配器，成员函数就是模板的容器，调用对应的功能。结构是堆，在插入调用容器的插入功能后，要向上调整堆。删除堆顶元素后，要向下调整堆，保证堆顶元素时最值。看看标准库需要什么模板
首先是变量的类型，容器的种类，最后是一个仿函数
仿函数
仿函数的本质是一个类，它重载了函数调用符 () ,当这个类的对象使用()时，就调用了自己写的函数
优先队列需要两个仿函数，是大小比较的，一个从小到大，一个从大到小。传入模板T类型返回比较结果
template <typename T>
struct less
{
bool operator()(const T& x1, const T& x2)
{
return x1 < x2;
}
};
有了仿函数，优先队列的类的写法和之前的栈这些一样，只需要调用容器对应的功能。调整堆的写法在数据结构展示过，过程基本差不多，这是大小比较这里用仿函数
代码
#pragma once
namespace my_queue
{
template <typename T>
struct less
{
bool operator()(const T& x1, const T& x2)
{
return x1 < x2;
}
};
template <typename T>
struct greater
{
bool operator()(const T& x1, const T& x2)
{
return x1 > x2;
}
};
template <class T, class container = vector<T>, class compare = less<T>>
class priority_queue
{
public:
void adjust_up(int child)
{
compare com;
int parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
}
else
{
return;
}
child = parent;
parent = (child - 1) / 2;
}
}
void adjust_down(int parent)
{
compare com;
int child = parent * 2 + 1;
while (child < _con.size())
{
//需判断右孩子是否越界
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
child++;
}
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
}
else
{
break;
}
parent = child;
child = parent * 2 + 1;
}
}
void push(const T& x)
{
_con.push_back(x);
adjust_up(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjust_down(0);
}
T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
container _con;
};
}
仿函数的用法
对于自定义类，这里的仿函数会调用类的比较的重载。而对于类的指针，仿函数不一定只能用默认的大小比较，也可以自己实现一个仿函数，传入优先队列，就会调用自己的比较功能
下面是一个日期类
class Date
{
public:
Date(int year = 1900, int month = 1, int day = 1)
: _year(year)
, _month(month)
, _day(day)
{}
bool operator<(const Date& d)const
{
return (_year < d._year) ||
(_year == d._year && _month < d._month) ||
(_year == d._year && _month == d._month && _day < d._day);
}
bool operator>(const Date& d)const
{
return (_year > d._year) ||
(_year == d._year && _month > d._month) ||
(_year == d._year && _month == d._month && _day > d._day);
}
friend ostream& operator<<(ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
实现仿函数，传入优先队列，就可以自己实现比较功能
//仿函数
struct __date_less
{
bool operator()(const Date* d1, const Date* d2)
{
return *d1 < *d2;
}
};
//传入
priority_queue <Date*, vector<Date*>, __date_less> que;
que.push(new Date(2018, 10, 29));
que.push(new Date(2018, 10, 28));
que.push(new Date(2018, 10, 30));
cout << *(que.top()) << endl;
