在本次项目中我们的目标是**模拟实现一个**priority\_queue,先一起看一下C++标准文档中priority\_queue的定义:[cplusplus : C++ priority\_queue标准文档](https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue)
https://legacy.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue
总结一下:
更多有关**数据结构——堆**相关的基础知识可以移步:[【数据结构】什么是堆?](https://blog.csdn.net/weixin_72357342/article/details/134904555)
https://blog.csdn.net/weixin_72357342/article/details/134904555 文章目录如下:
在本次项目中我们的目标是**实现一个**priority\_queue容器适配器: 该priority\_queue容器适配器底层可以使用vector或deque来实现,但是单独分别使用vector或deque来实现一个堆太过麻烦,我们不如借助模板来一次性实现既可以使用顺序底层的堆,又可以实现deque底层的堆: priority\_queue提供的**功能**有:
通过第一部分对项目功能的介绍,我们已经对priority_queue的功能有了大致的了解,虽然看似需要实现的功能很多,貌似一时间不知该如何下手,但我们可以分步分模块来分析这个项目的流程,最后再将各部分进行整合,所以大家不用担心,跟着我一步一步分析吧!
!!!注意,该部分的代码只是为了详细介绍某一部分的项目实现逻辑,故可能会删减一些与该部分不相关的代码以便大家理解,需要查看或拷贝完整详细代码的朋友可以移步本文第三部分。
因为priority\_queue的底层是用vector或deque来实现的,所以我们**只需要定义一个vector或deque成员变量**即可.但因为我们选择将priority\_queue写成类模板,所以这里成员变量的类型是模板类型. 其实可以理解为priority\_queue的底层就是一个vector或deque,但我们**通过类的特性,对vector或deque进行进一步的封装,使其行为符合priority\_queue的行为,就完成了一个priority\_queue类**.
该部分功能实现代码如下:
namespace mfc
{
template<class T, class Container = vector<T>, class Comapre = less<T>>
//这里模板的最后一个参数是控制堆模板是排大堆还是小堆的,是一种仿函数
class priority_queue
{
private:
//成员变量和成员函数子函数
Container _con;
public:
//成员函数
};
}
使用一个迭代区间来初始化堆, 其实就是**把这个迭代区间的元素拷贝存入堆中**, **再根据堆的特性将这些元素建成大堆或小堆**即可. 注意, 迭代器的类型有很多种, 我们可以直接将构造函数写成函数模板. 下图是在数据结构堆博客截取的向上建堆的图示过程, 方便大家理解建堆的过程:
综上所述,该部分代码如下:
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);//按迭代器顺序将数据插入堆中
++first;
}
//建堆 (size-1是下标,再-1是最后一个非叶子结点的公式)
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i);//向下调整建堆
}
}
因为我们前面实现了迭代区间初始化构造函数,编译器就**不会再给我们生成默认的无参构造函数**,这样会导致我们如果后续使用默认构造时出现一些问题:
因此我们把无参构造函数补充上,代码如下:
priority_queue()
{}
priority\_queue的push()就是**在容器尾部插入一个元素**,因为底层的vector或deque都实现有尾插函数push\_back(),所以我们直接调用就可以,但是直接就在尾部插入的话,**会破环堆的结构.导致其不符合大顶堆/小顶堆的特性**,所以我们要**将每个新插入的元素向上调整**到合适的位置才可以,代码如下:
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);//向上调整函数
}
因为我们不能保证新入的元素一定完全**符合堆定义的要求**,为了**防止新插入的元素破坏堆的性质**,因此我们**需要对新入堆的元素进行向上调整**,直到调整到其满足堆排序的性质为止.
为了方便理解,我们拿刚才的大堆做一下演示,**逻辑图示**如下:
实现代码如下:
void AdjustUp(int child)
{
Comapre com;//控制大堆还是小堆的仿函数变量
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))//com会根据仿函数的类型来套用相应的仿函数
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
因为priority\_queue的特性使得**堆顶元素一定为当前堆中最大/小的值**,因此我们**出堆操作往往需要出的是堆顶元素**.
但是我们**不能直接将堆顶元素删除**,因为这样**会导致堆中剩下的元素关系全部乱掉**:
后面剩余的数据也完全不符合大堆/小堆的特性:
因此**合理的操作**是**出堆顶就将堆顶元素和堆尾元素交换**,然后**将新堆顶元素向下调整到合适的位置上**:
代码如下:
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back(); //删掉最后一个元素
AdjustDown(0); //将堆顶元素(即0号位置元素)向下调整到合适的位置
}
因为我们不能保证换到堆顶的元素一定完全**符合堆定义的要求**,为了**防止新换上的元素破坏堆的性质**,因此我们**需要对新换上的元素进行向下调整**,直到调整到其满足堆排序的性质为止. 为了方便理解,我们拿刚才的大堆做一下演示,**逻辑图示**如下: 首先是**交换堆顶和堆尾元素**:
其次**将交换后的新堆顶元素和两个孩子做比较**,如果是**大堆**,那么**只要孩子比新堆顶元素大**,二者就**交换位置**,如果**两个孩子都比堆顶元素大**,则**堆顶元素和较大的那个孩子交换位置**:
直到**向下调整到叶子结点位置**或**交换到该堆顶元素比两个孩子结点都大**时**停止向下调整**:
注意: **向上调整我们只需要将入堆元素与它的双亲结点比较**,而**向下调整时我们需要先比较出结点的两个孩子的大小,然后双亲结点与大的/小的(取决于大堆还是小堆)孩子交换位置**,直到将该结点交换至叶子结点或比两个孩子结点都大/小为止.
代码如下:
void AdjustDown(int parent)
{
Comapre com;
//找左右孩子大的那个
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))//写死就固定是大堆还是小堆了,传模板可以达到自定义的效果
{
++child;
}
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
priority\_queue的top()函数就是**获取堆顶的元素**,vector和deque都有重载operator[]函数,我们可以直接调用它来取到堆顶元素,代码如下:
const T& top()
{
return _con[0];
}
priority\_queue的size()函数同样可以直接调用底层容器的size()函数,代码如下:
size_t size()
{
return _con.size();
}
priority\_queue的empty()函数同样可以直接调用底层容器的empty()函数,代码如下:
bool empty()
{
return _con.empty();
}
因为**模板定义和声明不能分离**,所以我们将程序运行的代码分别在**两个工程文件中**编辑,完整代码如下:
#include<iostream>
#include<vector>
using namespace std;
#include"PriorityQueue.h"
int main()
{
mfc::test_priority_queue();
return 0;
}
namespace mfc
{
template<class T, class Container = vector<T>, class Comapre = less<T>>
class priority_queue
{
private:
void AdjustDown(int parent)
{
Comapre com;
//找左右孩子大的那个
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))//写死就固定是大堆还是小堆了,传模板可以达到自定义的效果
{
++child;
}
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
Comapre com;
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (com(_con[parent], _con[child]))
{
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
public:
priority_queue()
{}
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
++first;
}
//建堆 (size-1是下标再-1是最后一个非叶子结点的公式)
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(i);
}
}
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);
}
const T& top()
{
return _con[0];
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
private:
Container _con;
};
void test_priority_queue()
{
priority_queue<int,vector<int>,greater<int>> pq;//传greater是小堆,默认是less大堆
pq.push(3);
pq.push(1);
pq.push(5);
pq.push(7);
pq.push(2);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
}
测试结果:
希望这篇priority_queue的模拟实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!