【priority_queue的使用及模拟实现】—— 我与C++的不解之缘（十六）

🕗 发布于 2024-11-18 07:29 c++ 开发语言 priority_queue

前言

priority_queue，翻译过来就是优先级队列，但是它其实是我们的堆结构（如果堆一些遗忘的可以看一下前面的文章复习一下【数据结构】二叉树——顺序结构——堆及其实现_二叉树顺序结构-CSDN博客），本篇文章就来使用并且模拟实现一下priority_queue。

`priority_queue`的使用

在这里插入图片描述

这个容器接口就这些，使用起来比较简单：这里就简单使用一下。

int main()
{
priority_queue<int> pq1;//无参构造
int arr[] = { 1,5,8,9,2,10,6 };
//使用一段迭代器区间构造(这里可以使用数组,因为原始指针可以像迭代器那样使用)
priority_queue<int> pq2(arr, arr + sizeof(arr) / sizeof(arr[0]));
//依次输出pq2
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;

//往pq1插入数据
pq1.push(1);
pq1.push(5);
pq1.push(7);
pq1.push(8);
pq1.push(9);
//依次输出pq1
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
return 0;
}

输出结果如下：

10 9 8 6 5 2 1
9 8 7 5 1

经过观察，我们会发现，默认构建的都是大堆，先看一下容器priority_queue 的定义

在这里插入图片描述

这里有三个模版参数，第一个是数据类型，第二个是容器类型（默认是vector)，第三个是compare 默认是 less（这个是一个仿函数，再模拟实现后面再讲解）。

我们不难发现，只有第三个模版参数才也可能控制是大堆还是小堆，（这里，我们如果要建小堆传**greater**即可）。

//建小堆
int main()
{
priority_queue<int, vector<int>, greater<int>> pq1;
pq1.push(9);
pq1.push(7);
pq1.push(5);
pq1.push(3);
pq1.push(2);
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
return 0;
}

2 3 5 7 9

这样就建了小堆；对于仿函数，在模拟实现之后，我相信就会有了深刻的理解。

`priority_queue`模拟实现

通过看priority_queue的定义，我们不难发现其也是一个容器适配器，默认容器是vector；所以它的成员变量就是一个容器，其的每一个操作就是在容器中进行一系列操作。

先来看一下priotity_queue的大致内容：

namespace HL
{
//默认——大堆
template<class T, class Contianer = vector<T>, class Compare = less<T>>
class priority_queue
{
//向下调整算法
void AdjustDown(int parent)
{}
//向上调整算法
void AjustUp(int child)
{}
public:
//默认构造
priority_queue() {}
//迭代器区间构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{}
void push(const T& x) {}
void pop() {}
T& top() {}
const T& top()const {}
size_t size()const {}
bool empty()const {}
private:
Contianer _con;
};
}

1、向上调整算法

所谓向上调整算法，就是向上调整当前节点，使其满足堆结构。

主要应用：插入节点时，最后一个节点（插入的节点）向上调整。

//向上调整算法
void AjustUp(int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (_con[parent] < _con[child])
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
child = parent;
parent = (child - 1) / 2;
}
}

2、向下调整算法

所谓向上调整算法，就是向下调整当前节点，使其满足堆结构。

主要应用：

构造堆结构时，从最后一个节点的父节点开始依次向下调整，创建堆结构。
删除节点时，第一个（堆顶）与最后一个（堆底）交换，然后让第一个（堆顶）节点向下调整。

void AdjustDown(int parent)
{
int child = 2 * parent + 1;
while (child < _con.size())
{
if (child < _con.size() - 1 && _con[child] < _con[child + 1])
{
child++;
}
if (_con[parent] < _con[child])
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
parent = child;
child = 2 * parent + 1;
}
}

3、构造函数

构造函数有两种，一是默认构造函数，另一个就是使用迭代器区间构造。

1.默认构造

//默认构造
priority_queue() {}

2.迭代器区间构造

迭代器区间，这里就先将数据插入到容器（vector）中，再从最后一个节点的父节点开始，依次往下调整建堆即可。

//迭代器区间构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}

4、push、pop、top

push: 插入数据，然后向上调整，保持堆结构。

void push(const T& x) 
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}

pop: 删除数据（删除堆顶数据），堆顶数据与堆低数据交换，然后从堆顶位置向下调整即可。

void pop() 
{
std::swap(_con[0], _con[_con.size() - 1]);
AdjustDown(0);
}

top: 返回堆顶数据

T& top() 
{
return _con[0];
}
const T& top()const 
{
return _con[0];
}

5、size、empty、swap

size: 返回堆中的数据个数

size_t size()const 
{
return _con.size();
}

empty: 判断堆是否为空

bool empty()const 
{
return _con.empty();
}

swap: 交换函数

void swap(priority_queue& pq)
{
std::swap(_con, pq._con);
}

到这里，priority_queue 大致就实现成功了一半，因为这里我们只实现了大堆。

接下来，我们来看一下仿函数，如何实现大小堆。

仿函数

仿函数，也是STL中比较中要的内容；

那为什么叫做仿函数呢？因为，他实际上是一个类，这个类重载了operator() 这样，我们就可以像函数应用实使用这个类。

先来看一下仿函数**less**：

//这里可以使用struct（默认成员是共有）
template<class T>
class Less
{
     public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};

这里实现了仿函数**Less** 和**Greater**，我们可以像函数那样去使用这个类。

int main()
{
HL::Less<int> l;
cout << (l(11, 22)) << endl;
return 0;
}

greater 与less类似，greater 是判断大的（就是，返回的是 x>y)。

知道了仿函数，再回头看一下**priority_queue** 第三个模板参数，这个模板参数就是来控制大小堆的（默认是less，就是大堆；如果我们传greater 就是小堆。）

这样我们再修改一下，向上调整算法和向下调整算法，让我们可以通过这个模板参数来控制大小堆。

//向下调整算法
void AdjustDown(int parent)
{
Compare com;
int child = 2 * parent + 1;
while (child < _con.size())
{
//if (child < _con.size() - 1 && _con[child] < _con[child + 1])
if (child < _con.size() - 1 && com(_con[child], _con[child + 1]))
{
child++;
}
//if (_con[parent] < _con[child])
if (com(_con[parent] , _con[child]))
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
parent = child;
child = 2 * parent + 1;
}
}
//向上调整算法
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (parent >= 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent] , _con[child]))
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
child = parent;
parent = (child - 1) / 2;
}
}

这里测试一下，使用模拟实现的堆进行排序，pq1建大堆，排降序；pq2建小堆，排升序。

void test_priority_queue()
{
HL::priority_queue<int,vecotr<int>, HL::Less<int>> pq1;
pq1.push(1);
pq1.push(7);
pq1.push(3);
pq1.push(5);
pq1.push(9);

while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
int arr[] = { 1,3,5,7,9,8,6,4,2 };
HL::priority_queue<int,vector<int>,HL::Greater<int>> pq2(arr, arr + sizeof(arr) / sizeof(arr[0]));
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
}
int main()
{
test_priority_queue();
return 0;
}

9 7 5 3 1
1 2 3 4 5 6 7 8 9

到这里，priority_queue 使用以及模拟实现就完成了，感谢各位的支持。

继续加油！！！

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

Greater<int>> pq2(arr, arr + sizeof(arr) / sizeof(arr[0]));
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
}
int main()
{
test_priority_queue();
return 0;
}

9 7 5 3 1
1 2 3 4 5 6 7 8 9

到这里，priority_queue 使用以及模拟实现就完成了，感谢各位的支持。

继续加油！！！

我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws

原文地址：https://blog.csdn.net/LH__1314/article/details/143831247

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Node.js | pnpm下载安装与环境配置
下一篇：3、PyTorch张量的运算API（下）

Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
Windows电脑本地部署llamafile并接入Qwen大语言模型远程AI对话实战
阅读更多2024-11-23
解决vm虚拟机中ctrl键粘滞问题（一直处于按下状态）
虚拟机中点击鼠标左键没有问题，单独按下键盘也没有问题，但是如果按下键盘的同时在按下鼠标左键就会卡住。而且100%稳定复现。发现问题原因：vm版本的问题，我的版本是17.5.0，升级成17.5.2 bu
阅读更多2024-11-23
第十章 JavaScript的应用
10.1.1 JavaScript简介1 简单性JavaScript 设计之初就考虑到了非专业程序员的使用，因此它的语法相对简单，容易上手。2 动态性JavaScript 是一种解释型语言，代码可以在
阅读更多2024-11-23
非root用户安装CUDA
4.下载完成后执行.run文件，需要添加两个参数，一个是--override，用于跳过某些检查或限制；另一个是--toolkitpath，它表示安装路径，必须是自己目录下面的路径，如果是根目录就会安装
阅读更多2024-11-23
Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
【代码】## Python操作neo4j库py2neo使用之py2neo 删除及事务相关操作（三）
阅读更多2024-11-23
【通俗理解】Jensen不等式与变分分布q(z)在积分计算中的应用
Jensen不等式 #变分分布 #积分计算 #期望 #凸函数 #优化问题 #下界估计 #机器学习。
阅读更多2024-11-23
「Mac玩转仓颉内测版27」基础篇7 - 字符串类型详解
本篇将介绍 Cangjie 中的字符串类型，包括字符串的定义、字面量形式、插值表达、常用操作及应用场景，帮助开发者熟练掌握字符串的使用。
阅读更多2024-11-23
数据科学与SQL：组距分组分析 | 区间分布问题
绝对值分布分析也可以理解为组距分组分析。对于某个指标而言，一个记录对应的指标值的绝对值，肯定落在所有指标值的绝对值的最小值和最大值构成的区间内，根据一定的算法，在把这个区间划分为等距离的几个小区间，，
阅读更多2024-11-23
c++编译报C1004错误的原因及解决办法
可能是你的代码文件最后没有正确的结束符，或者是缺少了一些必要的头文件或语句。默认磁盘驱动器没有足够的空间用于临时文件，需要大约两倍于源文件的空间。编译器到达了源文件尾但未解析构造。计算结果为假的 #i
阅读更多2024-11-23
mysql 去重补全取出重复变量函数和存储过程
mysql 去重补全取出重复变量函数和存储过程
阅读更多2024-11-23

【priority_queue的使用及模拟实现】—— 我与C++的不解之缘（十六）

前言