文章目录
前言
承接上一篇容器适配器的内容，本篇我们再来学一个优先级队列！
学习它需要我们对之前的堆的内容有一个较为全面的掌握，如果你不是很有信心的话，我建议你回去看看
正文开始！
一、优先级队列的使用
介绍
我们需要对其有一个这样的认识：
-
优先队列是一个容器适配器，根据严格的弱排序标准，它的第一个元素总是它所含的元素中最大的
-
此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
-
优先级队列已经不能称为队列，不符合FIFO特性拉
-
优先队列被实现为容器适配器，容器适配器即将特定的容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从特定容器的"尾部"弹出，其称为优先队列的顶部
-
底层容器可以是任何标准容器类模板，也可以是特定设计的容器类，容器应该可以通过随机访问迭代器访问，并支持以下操作：
-
empty():检测容器是否为空
-
size():返回容器中有效元素个数
-
front():返回容器中第一个元素的引用
-
push_back():在容器尾部插入元素
-
pop_back():删除容器尾部元素
-
标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector
-
需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_head,push_heap和pop_heap来自动完成此操作
我们来看看它的三个模板参数，第二个代表底层存储数据的容器，默认为vector，第三个就厉害了，这叫做仿函数（其实就是一个专门用作比较大小的类，我们后面会讲）
第二个容器必须支持随机访问迭代器（Random Access Iterator），以及 front()，push_back()，pop_back() 的操作
使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue
默认情况下，priority_queue用到的是大堆
#include <iostream>
#include <queue>
using namespace std;
int main()
{
//默认less 大堆
//如果要改建立小堆也很简单，第三个参数设置为greater<int>
priority_queue<int> pq;//实例化堆
pq.push(1);//插入值
pq.push(4);
pq.push(2);
pq.push(3);
//堆不为空时打印堆顶元素，大堆打印出来为降序
while (!pq.empty())
{
cout << pq.top() << " ";//打印堆顶元素
pq.pop();//删除堆顶元素
}
cout << endl;
return 0;
}
构造方式有两种，一种是直接构造一个空对象，另一种是通过迭代器区间去构造
一道题目
我们之前就说过，堆这种数据结构很适合处理TopK问题，比如说现在给你一个数组 nums 和大小 k ，请帮我求出这个数组第k大的数，你有没有什么思路？
答案是首先先建立一个大小为k的小堆（注意是小堆！！），那么堆顶元素必定是这k个数最小的，现在再把数组剩下的元素走一遍，如果比堆顶元素大，就pop一下，push新数据，这样走完后，小堆里的k个数必定是这个数组里面最大的k个数，而堆顶又是这k个数中最小的那个，即第k大数
力扣215.数组中的第k个最大元素
去试试吧！~
二、仿函数的讲解
对内置类型
仿函数是通过类中运算符重载()实现特定的功能，通过使用匿名对象使用，它的对象可以想函数一样去使用，使得很难区分是调用函数还是调用匿名对象
你可以顾名思义一下，仿函数就是用对象来模仿函数的一种方式，通过类来实现
// 定义一个仿函数模板类
template<class T>
struct Less
{
// 重载函数调用操作符
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
int main()
{
Less<int> lessfunc;//创建有名对象
cout << lessfunc(1, 2) << endl;//有名对象调用类成员函数
cout << lessfunc.operator()(1, 2) << endl;//显示调用
cout << Less<int>()(1, 2) << endl;//匿名对象，前面一个括号构造对象，后面调用函数
cout << Less<int>().operator()(1, 2) << endl;
return 0;
}
我们定义了一个名为 Less 的仿函数类，它重载了 operator() 来实现前面一个数是否小于后面一个数的功能
仿函数广泛用于C++标准库中，特别是在算法（std::sort）中作为比较函数或者操作函数，以及在容器（如 std::set 或者 std::map）中作为排序准则
仿函数的一个主要优点是它们可以保持状态，这意味着它们可以在多次调用之间保存和修改信息。这使得它们非常灵活和强大。此外，由于它们是类的实例，它们也可以拥有额外的方法和属性
对自定义类型
假设现在有个日期类
class Date
{
public:
Date(int year = 1970, 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 std::ostream& operator<<(std::ostream& _cout, const Date& d)
{
_cout << d._year << "-" << d._month << "-" << d._day;
return _cout;
}
private:
int _year;
int _month;
int _day;
};
创建数据为 Date 的优先级队列（大堆），取堆顶元素（判断是否能对自定义类型进行正确调整）
我们发现这是没问题的，因为在实际比较时，调用的是 Date 自己的比较逻辑
但是问题是我们经常存放的不是自定义类型，而是自定义类型的指针，这时候还能正常比较吗
答案是不行的，因为此时调用的是指针的比较逻辑，而指针所存储的地址是比较随机的，这时候一共有两种方法，一种是我们下篇要学的模板特化，一种就是专门为Date*写一个仿函数
//小于
template<class T>
struct pDateLess
{
bool operator()(const T& p1, const T& p2)
{
return (*p1) < (*p2);
}
};
//大于
template<class T>
struct pDateGreater
{
bool operator()(const T& p1, const T& p2)
{
return (*p1) > (*p2);
}
};
成功解决，很神奇吧！
三、模拟实现priority_queue
既然已经对优先级队列有了个大致的认识，不如我们再来好好实现一下它，对它有个更底层的认识！
优先级队列 priority_queue 属于容器适配器的一种，像栈和队列一样，没有迭代器，同时也不需要实现自己的具体功能，调用底层容器的功能就行了，不过因为堆比较特殊，需要具备 向上调整 和 向下调整 的能力，确保符合堆的规则
向上调整 和 向下调整 都是实现的一个难点，且为了避免与库里面的优先级队列冲突，我们把它封装到自己的命名空间里面
两个仿函数
明白了仿函数的概念和意义后，应该可以很自然的写出两种仿函数，并且我们要访问内部函数，干脆直接 struct 就行
template<class T>
struct Myless
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct Mygreater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
构造函数
因为有两种，一种用迭代器，一种为空，迭代器会覆盖掉默认的构造参数，我们这里借助default来强制生成默认构造函数
template<class T, class Container = vector<T>, class Compare = Myless<T>>
class priority_queue
{
public:
priority_queue() = default;
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
// 1.把数据全部存放到存储数据的容器中
while (first != last) {
_con.push_back(*first);
++first;
}
// 2.向下调整建堆，默认为大堆
for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
adjust_down(i);
}
}
private:
Container _con;
};
向上调整和向下调整
为了跟我们以前的堆的比较形成对比，我在每个使用仿函数的地方都给出了之前的语句
void adjust_up(int child)
{
Comapre comfunc;
int parent = (child - 1) / 2;
while (child > 0) {
//if (_con[parent] < _con[child]){
//if (comfunc.operator()(_con[parent], _con[child])){
if (comfunc(_con[parent], _con[child])) {
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void adjust_down(int parent)
{
Compare comfunc;
int child = parent * 2 + 1;
while (child < _con.size()) {
// 1.先选出左右孩子节点中较大的那个
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])) {
child += 1;
}
// 2.将较大的那个节点跟父节点比较
//if (_con[parent] < _con[child])
if (comfunc(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
插入数据和删除数据
这也要考验你对堆的了解是否深入了！
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);
}
其他常用接口
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
总概一览
namespace HQ
{
template<class T>
struct Myless
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct Mygreater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T, class Container = vector<T>, class Compare = Myless<T>>
class priority_queue
{
public:
priority_queue() = default;
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
// 1.把数据全部存放到存储数据的容器中
while (first != last) {
_con.push_back(*first);
++first;
}
// 2.向下调整建堆，默认为大堆
for (int i = (_con.size() - 2) / 2; i >= 0; i--) {
adjust_down(i);
}
}
void adjust_up(int child)
{
Comapre comfunc;
int parent = (child - 1) / 2;
while (child > 0) {
//if (_con[parent] < _con[child]){
//if (comfunc.operator()(_con[parent], _con[child])){
if (comfunc(_con[parent], _con[child])) {
swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else {
break;
}
}
}
void adjust_down(int parent)
{
Compare comfunc;
int child = parent * 2 + 1;
while (child < _con.size()) {
// 1.先选出左右孩子节点中较大的那个
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && comfunc(_con[child], _con[child + 1])) {
child += 1;
}
// 2.将较大的那个节点跟父节点比较
//if (_con[parent] < _con[child])
if (comfunc(_con[parent], _con[child])) {
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else {
break;
}
}
}
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);
}
const T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
使用效果如下：
总结
我写完这篇后，自认为还是蛮有成就感的，你呢？
标签：容器,const,17,parent,适配器,queue,child,size,con From： https://blog.csdn.net/2301_80392199/article/details/143141306