优先级队列(Priority Queue)
队列是一种特征为FIFO的数据结构，每次从队列中取出的是最早加入队列中的元素。但是，许多应用需要另一种队列，每次从队列中取出的应是具有最高优先权的元素，这种队列就是优先级队列(Priority Queue)，也称为优先权队列。
1. 优先级队列的概念
优先级队列的定义
优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
优先级队列的特点
优先级队列是0个或多个元素的集合，每个元素都有一个优先权或值。 当给每个元素分配一个数字来标记其优先级时，可设较小的数字具有较高的优先级，这样更方便地在一个集合中访问优先级最高的元素，并对其进行查找和删除操作。 对优先级队列，执行的操作主要有：(1)查找，(2)插入，(3)删除。 在最小优先级队列(min Priority Queue)中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素。 在最大优先级队列(max Priority Queue)中，查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。 插入操作均只是简单地把一个新的元素加入到队列中。 注：每个元素的优先级根据问题的要求而定。当从优先级队列中删除一个元素时，可能出现多个元素具有相同的优先权。在这种情况下，把这些具有相同优先权的元素视为一个先来先服务的队列，按他们的入队顺序进行先后处理。2.优先级队列的使用
头文件：#include < queue >
优先级队列默认是最大优先级队列
接口介绍
| 函数声明 | 函数说明 |
|---|---|
| priority_queue() / priority_queue(first, last) | 构造一个空的优先级队列 |
| empty( ) | 判断优先级队列是否为空，为空返回true |
| empty( ) | 判断优先级队列是否为空，为空返回true |
| top( ) | 获取优先级队列中最大或者最小的元素，即堆顶元素 |
| push(x) | 将x元素插入到优先级队列中 |
| pop() | 删除优先级队列中最大或者最小的元素， 即删除堆顶元素 |
测试代码：
void test()
{
priority_queue<int> pq;
pq.push(13);
pq.push(14);
pq.push(9);
pq.push(23);
pq.push(12);
pq.push(22);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
测试结果：默认是最大优先级队列，所以堆顶元素一直是最大的元素
如何将创建最小优先级队列----
优先级队列原型：
泛型介绍：T为优先级队列存储的数据类型；Container为优先级队列中存储数据的容器；Compare伪函数，决定是最大优先级队列还是最小优先级队列
template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;
创建最小优先级队列：
priority_queue<int, vector<int>, greater<int>> pq;
测试结果：
优先级队列存放自定义类型时，需要自定义类型支持比较的操作。
class A
{
public:
A(int a = 1)
:_a(a)
{}
//支持比较函数
bool operator<(const A& a) const
{
return _a < a._a;
}
bool operator>(const A& a) const
{
return _a > a._a;
}
int _a;
};
测试结果：
应用场景：Top-K问题
数组中的第K个最大元素
代码：
class Solution {
public:
int findKthLargest(vector<int>& nums, int k)
{
priority_queue<int> pq(nums.begin(), nums.end());
while (--k)
pq.pop();
return pq.top();
}
};
3.优先级队列的实现
标准容器类vector和deque(双端队列)满足实现优先级队列的需求，库中底层默认是使用Vector容器来实现的，我们现在就利用vector简单模拟实现
private: vector<T> con;
向下调整算法
向下调整算法用于优先级队列的删除接口的实现
void shiftDown()
{
int parent = 0;
int child = 2 * parent + 1;
while (child < con.size())
{
if (child + 1 < con.size() && con[child] < con[child + 1])
{
++child;
}
if (con[parent] < con[child])
{
swap(con[parent], con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
向上调整算法
向上调整算法用于优先级队列的插入接口的实现
//向上调整
void shiftUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (con[parent] < con[child])
{
swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
push()
-
将数据插入到容器的尾端
进行向上调整算法，建成堆
void push(const T& val)
{
//尾插
con.push_back(val);
shiftUp(con.size() - 1);
}
pop()
将收尾数据进行交换 删除末尾最后一个元素 进行向下调整算法，建成堆
void pop()
{
//交换
swap(con[0], con[con.size() - 1]);
con.pop_back();
shiftDown();
}
top()、size()、empty()
都直接使用容器中的接口实现
T& top()
{
return con.front();
}
size_t size() const
{
return con.size();
}
bool empty() const
{
return con.empty();
}
测试结果：
但是我们的实现非常的死板，首先是不能创建最小优先级队列，其次是不能像底层实现一样，可以选择多种容器来存储数据来实现。
解决普通的优先级队列的两个问题
解决只能通过vector< T >来存储数据的问题
我们可以通过容器多添加一个泛型来解决多种容器的存储
priority_queue可以通过 vector< T >、deque< T >实现
默认使用vector< T >
原因：
与之前代码需要修改的地方
1、泛型
template<class T, class Container = vector<T>>
2、所需要的容器
private: Container con;
解决只能创建最大优先级队列问题
解决办法，加入新的泛型，该泛型是一个伪函数
如果不知道什么是伪函数，可以看看什么是伪函数，以及伪函数的使用
大小堆创建的不同其实就是在实现向上调整和向下调整时元素比较的不同而已。
与之前代码需要修改的地方
1、需要创建两个仿函数类
//用大最小优先级队列
template<class T>
struct Less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
//用于最小优先级队列
template<class T>
struct Greater
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
2、加入新泛型
template<class T, class Container = vector<T>, class Compare = Less<T>>
private: Compare cmp;
3、利用仿函数，替代代码中关键的比较的地方
测试结果：
完整代码
//用大最小优先级队列
template<class T>
struct Less
{
bool operator()(const T& a, const T& b)
{
return a < b;
}
};
//用于最小优先级队列
template<class T>
struct Greater
{
bool operator()(const T& a, const T& b)
{
return a > b;
}
};
template<class T, class Container = vector<T>, class Compare = Less<T>>
class PriorityQueue
{
public:
//向下调整
void shiftDown()
{
int parent = 0;
int child = 2 * parent + 1;
while (child < con.size())
{
if (child + 1 < con.size() && cmp(con[child], con[child + 1]))
{
++child;
}
if (cmp(con[parent], con[child]))
{
swap(con[parent], con[child]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
//向上调整
void shiftUp(int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (cmp(con[parent], con[child]))
{
swap(con[parent], con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void push(const T& val)
{
//尾插
con.push_back(val);
shiftUp(con.size() - 1);
}
void pop()
{
//交换
swap(con[0], con[con.size() - 1]);
con.pop_back();
shiftDown();
}
T& top()
{
return con.front();
}
size_t size() const
{
return con.size();
}
bool empty() const
{
return con.empty();
}
private:
Container con;
Compare cmp;
};
