🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《C++》 《Linux》
❤️感谢大家点赞👍收藏⭐评论✍️
文章目录
- 前言
- 一、优先级队列的使用
- 1.1 基本功能
- 1.2 优先级模式切换
- 1.3 相关题目
- 二、模拟实现优先级队列
- 2.1 构造函数
- 2.2 基本功能
- 2.3 仿函数的使用
- 2.4 特殊场景
- 三、整体代码
前言
优先级队列 priority_queue 是容器适配器中的一种，常用来进行对数据进行优先级处理，比如优先级高的值在前面，这其实就是初阶数据结构中的 堆，它俩本质上是一样东西，底层都是以数组存储的完全二叉树，不过优先级队列 priority_queue 中加入了 泛型编程 的思想，并且属于 STL 中的一部分
一、优先级队列的使用
首先需要认识一下优先级队列 priority_queue
1.1 基本功能
优先级队列的构造方式有两种：直接构造一个空对象 和 通过迭代器区间进行构造
直接构造一个空对象
#include <iostream>
#include <vector> //优先级队列包含在 queue 的头文件中
#include <queue>
using namespace std;
int main()
{
priority_queue<int> pq; //直接构造一个空对象， 默认为大堆
cout << typeid(pq).name() << endl; // 查看类型
return 0;
}
注意： 默认比较方式为 less，最终为 优先级高的值排在上面（大堆）
通过迭代器区间构造对象
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
vector<char> v = { 'a', 'b', 'c', 'd', 'e' };
priority_queue<char, deque<char>, greater<char>> pq(v.begin(), v.end());
cout << typeid(pq).name() << endl << endl;
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
return 0;
}
注意： 将比较方式改为 greater 后，生成的是 小堆，并且如果想修改比较方式的话，需要指明模板参数 底层容器，因为比较方式位于模板参数最后，不能跳跃缺省（遵循缺省参数规则）
小测试：27,15,19,18,28,34,65,49,25,37 分别生成大堆与小堆
大堆
vector<int> v = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
priority_queue<int, vector<int>, less<int>> pq(v.begin(), v.end());
//priority_queue<int, vector<int>> pq(v.begin(), v.end()); //写法一样
小堆
vector<int> v = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
priority_queue<int, vector<int>, greater<int>> pq(v.begin(), v.end()); //生成小堆
接下来使用优先级队列（以大堆为例）中的各种功能：入堆、出堆、查看堆顶元素、查看堆中元素个数
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void Print(const priority_queue<int>& pq)
{
cout << "pq.empty(): " << pq.empty() << endl;
cout << "pq.size(): " << pq.size() << endl;
cout << "pq.top(): " << pq.top() << endl << endl;
}
int main()
{
vector<int> v = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
priority_queue<int, vector<int>> pq(v.begin(), v.end());
Print(pq);
pq.push(10);
pq.push(100);
Print(pq);
pq.pop();
pq.pop();
pq.pop();
Print(pq);
return 0;
}
1.2 优先级模式切换
创建优先级队列时，默认为 大堆，因为比较方式（仿函数）缺省值为 less，这个设计比较反人类，小于 less 是大堆，大于 greater 是小堆…
如果想要创建 小堆，需要将比较方式（仿函数）改为 greater
注意： 因为比较方式（仿函数） 位于参数3，而参数2也为缺省参数，因此如果想要修改参数3，就得指明参数2
priority_queue<int> pqBig; //大堆
priority_queue<int, vector<int>, greater<int>> pqSmall; //小堆
1.3 相关题目
优先级队列（堆）可以用来进行排序和解决 Top-K 问题，比如 查找第 k 个最大的值 就比较适合使用优先级队列
215. 数组中的第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
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
思路1：利用数组建立大小为 k 的小堆，将剩余数据与堆顶值比较，如果大于，就入堆
- 为什么建小堆？因为此时需要的是最大的值，建大堆可能会导致次大的值无法入堆
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
auto it = nums.begin() + k;
while (it != nums.end())
{
if (*it > pq.top())
{
pq.pop();
pq.push(*it);
}
++it;
}
return pq.top();
}
};
思路2：将数组排序，取第k个
bool myfunction (int i, int j)
{
return i > j;
}
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(),nums.end(), myfunction);
return nums[k - 1];
}
};
二、模拟实现优先级队列
优先级队列 priority_queue 属于容器适配器的一种，像栈和队列一样，没有迭代器，同时也不需要实现自己的具体功能，调用底层容器的功能就行了，不过因为堆比较特殊，需要具备 向上调整 和 向下调整 的能力，确保符合堆的规则
2.1 构造函数
注： 现在实现的是没有仿函数的版本
优先级队列的基本框架为
#pragma once
namespace Aron
{
//默认底层结构为 vector
template<class T, class Container = vector<T>>
class priority_queue
{
public:
private:
Container _con;
};
}
默认构造函数：显式调用底层结构的默认构造函数
priority_queue()
: _con()
{}
迭代器区间构造：将区间进行遍历，逐个插入即可
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: _con()
{
while (first != last)
{
push(*first);
first++;
}
}
测试：
void test_pq1()
{
vector<int> arr = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
priority_queue<int> pq(arr.begin(), arr.end());
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}
2.2 基本功能
因为是容器适配器，所以优先级队列也没有迭代器
同时基本功能也比较少，首先来看看比较简单的容量相关函数
容量相关
判断是否为空：复用底层结构的判空函数
bool empty() const
{
return _con.empty();
}
获取优先级队列大小：复用获取大小的函数
size_t size() const
{
return _con.size();
}
获取堆顶元素：堆顶元素即第一个元素（完全二叉树的根）
const T& top() const
{
return _con.front();
}
注意： 以上三个函数均为涉及对象内容的改变，因此均使用 const 修饰 this 指针所指向的内容
数据修改
因为在插入/删除数据后，需要确保堆能符合要求
- 大堆：父节点比子节点大
- 小堆：父节点比子节点小
因此每进行一次数据修改相关操作，都需要检查当前堆结构是否被破坏，这一过程称为 调整
插入数据：尾插数据，然后向上调整
void push(const T& val)
{
_con.push_back(val);
adjust_up(size() - 1);
}
向上调整：将当前子节点与父节点进行比较，确保符合堆的特性，如果不符合，需要进行调整
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child != 0)
{
if (_con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
注意： 如果在调整过程中，发现遵循堆的特性，那么此时不需要再调整，直接 break 即可
删除数据：将堆顶数据交换至堆底，删除堆底元素，再向下调整堆
void pop()
{
if (empty())
return;
std::swap(_con.front(), _con.back());
_con.pop_back();
adjust_down(0);
}
向下调整：将当前父节点与 【较大 / 较小】 子节点进行比较，确保符合堆的特性，如果不符合，需要进行调整
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < size())
{
if (child + 1 < size() && _con[child + 1] > _con[child])
child++;
if (_con[child] > _con[parent])
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
注意： 删除时，需要先判断当前堆是否为空，空则不执行删除
测试：
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
#include "priority_queue.h"
void Print(const Aron::priority_queue<int>& pq)
{
cout << "pq.empty(): " << pq.empty() << endl;
cout << "pq.size(): " << pq.size() << endl;
cout << "pq.top(): " << pq.top() << endl << endl;
}
int main()
{
vector<int> v = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
Aron::priority_queue<int, vector<int>> pq(v.begin(), v.end());
Print(pq);
pq.push(10);
pq.push(100);
Print(pq);
pq.pop();
pq.pop();
pq.pop();
Print(pq);
return 0;
}
假设先使用 小堆，需要将下图中的三处逻辑判断，改为 <
难道每次使用时都得手动切换吗？而且如果我想同时使用大堆和小堆时该怎么办？
- 答案是没必要，通过
仿函数可以轻松解决问题，这也是本文的重点内容
2.3 仿函数的使用
仿函数又名函数对象 function objects，仿函数的主要作用是 借助类和运算符重载，做到同一格式兼容所有函数 这有点像函数指针，相比于函数指针又长又难理解的定义，仿函数的使用可谓是很简单了
下面是两个仿函数，作用是比较大小
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
此时 priority_queue 中的模板参数升级为3个，而参数3的缺省值就是 less
template<class T, class Container = vector<T>, class Comper = less<T>>
当需要进行逻辑比较时（大小堆需要不同的比较逻辑），只需要调用 operator() 进行比较即可
这里采用的是匿名对象调用的方式，当然也可以直接实例化出一个对象，然后再调用 operator() 进行比较
在使用仿函数后，向上调整 和 向下调整 变成了下面这个样子
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child != 0)
{
if (Comper()(_con[parent], _con[child])) //匿名对象调用 operator()
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < size())
{
if (child + 1 < size() && Comper()(_con[child], _con[child + 1]))
child++;
if (Comper()(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
使用仿函数后，可以轻松切换为小堆
void Print(const Aron::priority_queue<int, vector<int>, Aron::greater<int>>& pq)
{
cout << "pq.empty(): " << pq.empty() << endl;
cout << "pq.size(): " << pq.size() << endl;
cout << "pq.top(): " << pq.top() << endl << endl;
}
int main()
{
vector<int> v = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
Aron::priority_queue<int, vector<int>, Aron::greater<int>> pq(v.begin(), v.end());
Print(pq);
pq.push(10);
pq.push(100);
Print(pq);
pq.pop();
pq.pop();
pq.pop();
Print(pq);
return 0;
}
注意： 为了避免自己写的仿函数名与库中的仿函数名起冲突，最好加上命令空间，访问指定域中的仿函数
仿函数作为 STL 六大组件之一，处处体现着泛型编程的思想
仿函数给我们留了很大的发挥空间，只要我们设计的仿函数符合调用规则，那么其中的具体比较内容可以自定义（后续在进行特殊场景的比较时，作用很大）
2.4 特殊场景
假设此时存在 日期类（部分）
class Date
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 的优先级队列（大堆），取堆顶元素（判断是否能对自定义类型进行正确调整）
void test_pq2()
{
priority_queue<Date> pq;
pq.push(Date(2013, 4, 30));
pq.push(Date(2014, 5, 30));
pq.push(Date(2024, 5, 1));
cout << pq.top() << endl;
}
结果：正确，因为在实际比较时，调用的是 Date 自己的比较逻辑，所以没问题
但如果此时数据为 Date*，再进行比较
结果：错误，多次运行结果不一样！因为此时调用的是指针的比较逻辑（地址是随机的，因此结果也是随机的）
解决方法：
- 通过再编写指针的仿函数解决
- 通过模板特化解决
这里介绍法1，法2在下篇文章《模板进阶》中讲解
仿函数给我们提供了极高的自由度，因此可以专门为 Date* 编写一个仿函数（曲线救国）
template<class T>
struct DateLess
{
bool operator()(const T& x, const T& y)
{
return *x < *y;
}
};
template<class T>
struct DateGreater
{
bool operator()(const T& x, const T& y)
{
return *x > *y;
}
};
在构建对象时，带上对对应的 仿函数 就行了
void test_pq3()
{
priority_queue<Date*, vector<Date*>, DateLess<Date*>> p1;
p1.push(new Date(2013, 4, 30));
p1.push(new Date(2014, 5, 30));
p1.push(new Date(2024, 5, 1));
cout << *(p1.top()) << endl;
priority_queue<Date*, vector<Date*>, DateGreater<Date*>> p2;
p2.push(new Date(2013, 4, 30));
p2.push(new Date(2014, 5, 30));
p2.push(new Date(2024, 5, 1));
cout << *(p2.top()) << endl;
}
关于 Date* 仿函数的具体调用过程，可以自己下去通过调试观察
三、整体代码
priority_queue.h
#pragma once
namespace Aron
{
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;
};
template<class T>
struct less
{
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
struct greater
{
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T>
struct DateLess
{
bool operator()(const T& x, const T& y)
{
return *x < *y;
}
};
template<class T>
struct DateGreater
{
bool operator()(const T& x, const T& y)
{
return *x > *y;
}
};
/*template<class T>
struct less<T*>
{
bool operator()(const T& x, const T& y)
{
return *x < *y;
}
};
template<class T>
struct greater<T*>
{
bool operator()(const T& x, const T& y)
{
return *x > *y;
}
};*/
template<class T, class Container = vector<T>, class Comper = less<T>>
class priority_queue
{
public:
priority_queue()
: _con()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
: _con()
{
while (first != last)
{
push(*first);
first++;
}
}
bool empty() const
{
return _con.empty();
}
size_t size() const
{
return _con.size();
}
const T& top() const
{
return _con.front();
}
void push(const T& val)
{
_con.push_back(val);
adjust_up(size() - 1);
}
void pop()
{
if (empty())
return;
std::swap(_con.front(), _con.back());
_con.pop_back();
adjust_down(0);
}
protected:
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child != 0)
{
if (Comper()(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
break;
}
}
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < size())
{
if (child + 1 < size() && Comper()(_con[child], _con[child + 1]))
child++;
if (Comper()(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
private:
Container _con;
};
void test_pq1()
{
vector<int> arr = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
priority_queue<int> pq(arr.begin(), arr.end());
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
}
void test_pq2()
{
priority_queue<Date> pq;
pq.push(Date(2013, 4, 30));
pq.push(Date(2014, 5, 30));
pq.push(Date(2024, 5, 1));
cout << pq.top() << endl;
}
void test_pq3()
{
priority_queue<Date*, vector<Date*>, DateLess<Date*>> p1;
p1.push(new Date(2013, 4, 30));
p1.push(new Date(2014, 5, 30));
p1.push(new Date(2024, 5, 1));
cout << *(p1.top()) << endl;
priority_queue<Date*, vector<Date*>, DateGreater<Date*>> p2;
p2.push(new Date(2013, 4, 30));
p2.push(new Date(2014, 5, 30));
p2.push(new Date(2024, 5, 1));
cout << *(p2.top()) << endl;
}
}
