[c++进阶(十)]priority_queue的模拟实现
1.前言
本章重点
本节着重讲解优先级队列的底层原理以及相关接口的模拟实现
2.什么是priority_queue
优先级队列默认的情况下是大堆。
优先级队列有三个函数模版，第一个是队列存储的类型，第二个是优先级队列底层使用的容器，第三个是仿函数，主要用来决定优先级队列里面谁的优先级更大，大的就排堆顶。
总结一下到底什么是优先级队列呢？
优先级队列简单来说就是一棵二叉树，但是这棵二叉树又被一定的条件约束，这个约束就是仿函数，也就是说二叉树的堆顶是由谁排。并且这个优先级队列可以理解成为尾进，头出的队列，即使要删除堆顶元素，也要把堆顶元素和尾部元素互换，再进行删除。
3.priority_queue的使用
优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。
3.1 priority_queue的构造
1.空构造
#include<iostream>
#include<queue>//队列
#include<vector>//数组
#include<functional>//比较符号，less 或 greater
using namespace std;
int main()
{
priority_queue<int> pq1;//构造一个空的优先级队列
}2.迭代器区间进行构造
vector<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(4);
priority_queue<int> pq2(v.begin(), v.end()) ;//用v的迭代器区间构造pq2默认构造的是大堆，如果想构造小堆的话，则可以修改优先级队列的第三个参数。
3.2 push函数
push函数其实比较简单，只需要调用底层容器vector的push_back就可以了。
实际上push函数的底层实现是：先在直接调用vector的push_back函数插入，然后再调用向上调整建堆的函数，向上调整这个数，插入完成之后他才能是一个合法的堆。
priority_queue<int> pq3;
pq3.push(6);//向优先级队列中插入元素
pq3.push(3);
pq3.push(9);
pq3.push(8);3.3 pop函数
pop函数比push函数稍微复杂一点，主要就是要先交换第一个值和最后一个值（第一个值即堆顶，最后一个值即堆尾）。然后删除堆尾这个值，再使用向下调整建堆的函数，来使他删除一个值之后还是堆。
pop函数调用：
pq3.pop();//删除优先级队列第一个元素向size empty 以及front函数使用起来就比较简单了，这里就不过多的介绍了。
4.priority_queue的模拟实现
priority_queue的模拟实现主要是对函数的三个模版进行使用和封装。
4.1 仿函数
priority_queue默认是大堆，那么该如何实现小堆呢？需要先了解仿函数。
仿函数其实简单理解就是一个重载了operator() 的类对象，通过重载了operator，可以向调用函数一样的调用这个类对象，所以就把他称为仿函数。仿函数的具体细节参考上面链接。
(1) 仿函数的优点
① 仿函数比函数指针的执行速度快，函数指针通过地址调用，而仿函数是对运算符operator进行自定义来提高调用的效率。
② 仿函数比一般函数灵活，可以同时拥有两个不同的状态实体，一般函数不具备此种功能。
③ 仿函数可以作为模板参数使用，因为每个仿函数都拥有自己的类型。
（2）缺点
① 需要单独实现一个类。
② 定义形式比较复杂。
（3）仿函数的实现
template<class T>
struct Less
{
bool operator()(const T& l, const T& s)
{
return l < s;
}
};
template<class T>
struct greater
{
bool operator()(const T& l, const T& s)
{
return l > s;
}
};仿函数的使用
int main()
{
less<int> lessInt;//定义一个仿函数类对象，参数类型指定为int
std::cout << lessInt(1, 3) << std::endl;//对仿函数的调用等价于std::cout << lessInt.operator()(1, 3) << std::endl;
}4.2 堆的向上调整和向下调整
1.堆的向上调整
2.堆的向下调整
代码如下：
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < size())
{
if (child + 1 < _con.size() && _con[child] <_con[child + 1] )
child++;
if (_con[child] <= _con[parent])
break;
else
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
}
}
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[parent] >= _con[child])
break;
else
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child-1)/2;
}
}
}4.3 push和pop函数
void push(const T& val)
{
_con.push_back(val);
if(_con.size()>1)
AdjustUp(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0); //将第0个元素进行一次向下调整
}4.4 总体代码
.h文件
#include <iostream>
#include <vector>
#include <deque>
using namespace std;
namespace njust
{
template<class T>
struct Less
{
bool operator()(const T& l, const T& s)
{
return l < s;
}
};
template<class T>
struct greater
{
bool operator()(const T& l, const T& s)
{
return l > s;
}
};
template<class T,class Container=vector<T>,class Cmp=Less<T>>
class Priority_Queue
{
public:
Priority_Queue()
{
}
template<class InputIterator>
Priority_Queue(InputIterator first, InputIterator end)
{
while (first != end)
{
_con.push_back(*first);
first++;
}
//建堆----时间复杂度O（n）
//默认情况下priority_queue是大堆，故我们这里排升序
for (size_t i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
{
//从第一个非叶子节点开始计算，因为叶子节点天然的就是合法的堆。
AdjustDown(i);//向下调整算法,建大堆
}
}
void push(const T& val)
{
_con.push_back(val);
if(_con.size()>1)
AdjustUp(_con.size() - 1);
}
void pop()
{
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
AdjustDown(0); //将第0个元素进行一次向下调整
}
bool empty()
{
return _con.empty();
}
T& top()
{
return _con[0];
}
size_t size()
{
return _con.size();
}
private:
//大堆
void AdjustDown(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < size())
{
if (child + 1 < _con.size() && _con[child] <_con[child + 1] )
child++;
if (_con[child] <= _con[parent])
break;
else
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
}
}
void AdjustUp(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_con[parent] >= _con[child])
break;
else
{
swap(_con[parent], _con[child]);
child = parent;
parent = (child-1)/2;
}
}
}
Container _con;//可以把_con直接理解成为vector
};
}.cpp文件
int main()
{
njust::Priority_Queue<int> pq;
pq.push(1);
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(5);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
return 0;
}5.本章总结
主要了阐述了优先级队列相关的函数接口如何实现，以及如何自己实现仿函数。笔者认为这一章最重要的就是向上向下调整建堆的过程，以及当使用一个迭代器区间进行初始化的时候，如何进行建堆，从哪个地方开始建。
原文地址：https://blog.csdn.net/weixin_62196764/article/details/142587479
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！