一、优先级队列
1.1介绍
优先级队列（Priority Queue）是一种特殊的数据结构，其并不满足队列先进先出的原则，它结合了队列和堆的特点，允许我们在其中插入元素，并且能够保证任何时候提取出的元素都是当前队列中具有最高（或最低）优先级的元素。在优先级队列中，每个元素都有一个关联的优先级值，这个值通常用于决定元素在队列中的相对位置。
基本特性：
-
插入（Enqueue）：可以向优先级队列中添加元素，新元素会被放置在正确的位置以保持队列的优先级特性。
-
删除（Dequeue/Peek）：从优先级队列中删除或查看优先级最高的元素（如果是最大优先级队列）或最低的元素（如果是最小优先级队列）。这一操作也称为取队首元素，但在优先级队列中，队首元素并不总是最先入队的元素，而是优先级最高的元素。
-
排序性质：优先级队列内的元素始终按照优先级排序，这意味着即使新元素不断加入，队列仍然能快速提供最高（或最低）优先级的元素。
优先级队列是一种非常实用的数据结构，适用于那些需要高效处理动态优先级数据的场景，它可以灵活地满足按照优先级而非简单时间顺序处理数据的需求。
1.2 使用介绍
定义：
template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue解释：
- T为数据的类型
- Container为容器适配器的类型，缺省值为vector<T>,也可以显示传queue等用数组实现的容器
- Compare是用来控制大小堆的，缺省值为less<T>为大堆，也可以传greater<T>,less与greater都是仿函数
常用接口：
| 函数声明 | 接口说明 |
| prioprity_queue() | 构造一个空的优先级队列 |
| empty() | 检测优先级队列是否为空，是返回true，否则返回 false |
| top() | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| 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;
}
二、priority_queue模拟实现及仿函数讲解
1. 结构
template<class T,class Container=vector<T>,class Cmp=Less<T>>
class priority_queue
{
private:
Container _con;//容器
Cmp _cmp;//仿函数对象
};
2.仿函数
仿函数是指一类特殊的类，这类类通过在其内部重载operator()运算符，使得该类的对象可以像普通函数一样被调用。当对仿函数对象进行“函数调用”时，实际上执行的是operator()成员函数。在向上调整与向下调整时，需要一个方式来如何比较大小，也就是控制大小堆，这个功能可以使用函数指针来实现，但C++更偏向于使用仿函数
注意如果要将自定义类型放入priority_queue中的话，一定要在自定义类型中重载<或者>
3.push
将数据插入容器尾部，通过向上调整法调整到合适位置
void push(const T& x)
{
_con.push_back(x);
adjustUp(_con.size()-1);
}
//向上调整算法
void adjustUp(size_t child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
//利用仿函数比较
if (_cmp(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}4.pop
交换交换堆顶与堆尾的元素，删除堆尾元素，并将堆头元素向下调整到合适位置
void adjustDown(size_t parent)
{
size_t child = parent * 2 + 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 = child * 2 + 1;
}
else
{
break;
}
}
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjustDown(0);
}5.empty
bool empty()
{
return _con.empty();
}6.size
const size_t size() const
{
return _con.size();
}7.top
const T& top() const
{
return _con[0];
}完整代码：
#include<vector>
using namespace std;
namespace zyq
{
template<class T,class Container=vector<T>,class Cmp=Less<T>>
class priority_queue
{
public:
void adjustUp(size_t child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (_cmp(_con[parent], _con[child]))
{
swap(_con[parent], _con[child]);
child = parent;
parent = (parent - 1) / 2;
}
else
{
break;
}
}
}
void adjustDown(size_t parent)
{
size_t child = parent * 2 + 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 = child * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& x)
{
_con.push_back(x);
adjustUp(_con.size()-1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
adjustDown(0);
}
bool empty()
{
return _con.empty();
}
const size_t size() const
{
return _con.size();
}
const T& top() const
{
return _con[0];
}
private:
Container _con;
Cmp _cmp;
};
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;
}
};
}
