admin管理员组文章数量:1606968
【C++】---STL容器适配器之priority_queue
- 一、什么是priority_queue
- 二、priority_queue的使用
- 1、priority_queue的构造
- 2、push()
- 3、pop()
- 4、size()
- 5、empty()
- 三、priority_queue的模拟实现
- 1、仿函数
- (1)概念
- (2)优点
- (3)缺点
- (4)实现
- 2、堆的插入、删除
- 3、代码实现
- (1)仿函数<
- (2)仿函数>
- (3)push()
- (4)pop()
- (5)top()
- (6)size()
- (7)empty()
- 4、完整代码段
- (1)priority_queue_simulation.h
- (2)Test.cpp
一、什么是priority_queue
(1)priority_queen是一种:优先级队列,是一种常见的容器适配器,默认情况下把最大的元素放在第1位。
(2)它的底层是用堆实现的,默认情况下是大堆。可以随时插入元素,快速查找到队列中最大的元素。
(3)优先级队列从特定容器的尾部弹出,称为优先级队列的顶部。
(4) priority_queue的底层容器可以是任何标准容器的类模板,也可以是其他特定设计的容器类。反正底层容器必须要满足,通过迭代器进行随机访问,还要满足以下操作:
empty( ):检测容器是否为空
size( ):返回容器中有效元素个数
front( ):返回容器中第一个元素的引用
push_back( ):在容器尾部插入元素
pop_back( ):删除容器尾部元素
(5)标准容器类vector和deque都满足这些需求,在没有指定标准容器来进行实例化的时候,我们就用vector,因为堆的物理结构就是一个数组,所以说优先级队列就用vector来当做底层的容器类模板。
(6)需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。
二、priority_queue的使用
priority_queue的底层就是用vector容器做的类模板,在vector容器的基础上加了堆算法,进而形成了 priority_queue的底层模板容器,所以优先级队列:priority_queue就是堆 ,有所有需要用到堆的地方就可以考虑用priority_queue
1、priority_queue的构造
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int main()
{
priority_queue<int> p1;
p1.push(3);
p1.push(1);
p1.push(4);
p1.push(5);
p1.push(2);
while (!p1.empty())
{
cout << p1.top() << " ";
p1.pop();
}
cout << endl;
return 0;
}
2、push()
void push (const value_type& val);//向优先级队列中插入元素
priority_queue<int> pq3;
pq3.push(6);//向优先级队列中插入元素
pq3.push(3);
pq3.push(9);
pq3.push(8);
3、pop()
删除优先级队列第一个元素 :
void pop();//删除优先级队列第一个元素
pq3.pop();//删除优先级队列第一个元素
4、size()
返回优先级队列的元素个数:
size_type size() const;//返回优先级队列的元素个数
cout << pq3.size() << endl;//返回pq3的元素个数
5、empty()
判断优先级队列是否为空:
bool empty() const;//判断优先级队列是否为空
cout << pq3.empty() << endl;
三、priority_queue的模拟实现
priority_queue底层用堆实现,priority_queue的模拟实现只需要对堆进行封装即可。
1、仿函数
在默认情况下,priority_queue是大堆,但是我们如何实现小堆呢?这里我们就需要引用一个仿函数的概念来帮助我们实现。
(1)概念
什么是:仿函数?仿函数类 ,的对象 ,就是仿函数。
①仿函数就是让一个类的使用,看上去像函数。
②仿函数是在一个类的基础上进行打造的,在这个类里面对operator()进行了重载,使这一个类具有了函数的行为,所以我们称它为仿函数类。
③目的:是让 一个函数 -> 拥有类的性质。
(2)优点
①仿函数的效率比函数指针快。函数指针是通过地址进行调用,而仿函数是通过类里面重载的operator()进行调用。
②仿函数比一般函数灵活,它可以同时拥有两个不同状态的实体。
③仿函数可以作为模板参数使用,因为每个仿函数都拥有自己的类型。
(3)缺点
① 需要单独实现一个类。
② 定义形式比较复杂。
(4)实现
①:先看看以下代码,实现了对<的函数
bool isless(int l, int r)
{
return l < r;
}
int main()
{
cout << isless(1, 3) << endl;
return 0;
}
②:如果把这个函数写进类里面,那么这个类就是仿函数类,它的对象就是仿函数。
struct Less
{
bool operator()(int l,int r)
{
return l < r;
}
};
int main()
{
cout << isless(1, 3) << endl;
return 0;
}
③:加上类模板,支持不同类型的数据可以进行比较
template<class T>
struct Less
{
bool operator()(const T& l,const T& r)
{
return l < r;
}
};
int main()
{
cout << isless(1, 3) << endl;
return 0;
}
如何使用仿函数呢?!
template<class T>
struct Less
{
bool operator()(const T& l,const T& r)
{
return l < r;
}
};
int main()
{
Less<int> ls;// 通过仿函数类,定义一个对象,这个对象就叫做仿函数。
cout << ls(1, 3) << endl;// 这个仿函数可以像正常函数一样去使用,为什么?因为这里重载了operator()
//当我们不知道仿函数的概念的时候,我们就认为这是正常的函数传参。
return 0;
}
priority_queue模板中的less替换成greater就可以实现>的比较了:
template <class T, class Container = vector<T>,
class Compare = greater<typename Container::value_type> > class priority_queue;
2、堆的插入、删除
要对priority_queue插入删除,就是在堆上插入删除,堆在物理上是数组,在逻辑上是一颗完全二叉树!
(1)堆的插入(先插入,再向上调整)
(2)堆的删除(先交换,然后删除,再向下调整)
3、代码实现
priority_queue类默认的Container是vector,是自定义类型。因此priority_queue的构造函数、拷贝构造函数、赋值运算符重载函数、析构函数都不用写,会调vector的默认构造函数、拷贝构造函数、赋值运算符重载函数、析构函数。只需要实现7个函数:仿函数<、仿函数>、push、pop、top、size、empty。
(1)仿函数<
// 仿函数
// 仿函数的对象,可以像函数一样去使用
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
(2)仿函数>
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
(3)push()
template<class T, class Container = vector<T>,class Compare = yjl::less<T>>//指定Compare方式是less,按<比较
class priority_queue
{
public:
//向上调整算法
void AdjustUp(size_t child)
{
Compare com;//定义仿函数类对象
size_t parent = (child - 1) / 2;//找父亲的位置
while (child > 0)
{
//if (_con[parent] < _con[child])//父亲比孩子小,孩子就要往上提
if (com(_con[parent] , _con[child]))//使用仿函数比较
{
swap(_con[parent], _con[child]);//交换父亲和孩子
child = parent;//父亲变孩子
parent = (child - 1) / 2;//重新计算新孩子的父亲位置
}
else
{
//父亲>=孩子就不用动
break;
}
}
}
//插入
void push(const T& x)
{
_con.push_back(x);//尾插到堆
AdjustUp(_con.size() - 1);//向上调整
}
private:
Container _con;
};
(4)pop()
//向下调整算法
void AdjustDown(size_t parent)
{
Compare com;//定义仿函数类对象
size_t child = 2 * parent + 1;//找孩子位置
while (child < _con.size())
{
//找大孩子
if (child + 1 < _con.size() && _con[child+1] > _con[child])
{
child++;
}
//if(_con[parent] < _con[child])父亲比孩子小,父亲就要往下挪
if (com(_con[parent], _con[child]))//使用仿函数比较
{
swap(_con[parent], _con[child]);//交换父亲和孩子
parent = child;//孩子变父亲
child = parent * 2 + 1;//重新计算孩子的位置
}
else
{
break;
}
}
}
//删除
void pop()
{
swap(_con[0], _con[_con.size() - 1]);//交换堆顶元素和堆尾元素
_con.pop_back();//删除堆顶元素
AdjustDown(0);//向下调整算法
}
(5)top()
//返回priority_queue第一个元素,即堆顶元素
T top()
{
return _con[0];
}
(6)size()
//求priority_queue队列中元素个数
size_t size()
{
return _con.size();
}
(7)empty()
//判断priority_queue是否为空
bool empty()
{
return _con.empty();
}
4、完整代码段
(1)priority_queue_simulation.h
// 仿函数
// 仿函数的对象,可以像函数一样去使用
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;
}
};
/// 我们规定Greater模仿的是:大堆 (并且判断的时候孩子在前,父亲在后。)
/// 我们规定less模仿的是:小堆 (并且判断的时候孩子在前,父亲在后。)
template<class T, class Container = vector<T>,class Compare= greater<T>>
class priority_queue
{
private:
Container _con;
Compare cm;
public:
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
// if(com(_con[child],_con[parent]))// 这里调用了,greater中重载的operator()
// 函数对象com 可以向函数一样去调用函数:仿函数!!!
//if (_con[child] > _con[parent])
if (cm(_con[child] , _con[parent]))
{
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;// 先假定child 为左孩子 为较大的!
while (child < _con.size())
{
// 如果 右孩子存在 && 右孩子是两个孩子中较大的
if (child + 1 < _con.size() && cm(_con[child + 1] , _con[child]))
{
child++;
}
// 较大的孩子跟父亲交换,然后不断地迭代
//if (_con[child] > _con[parent])
if (cm(_con[child] , _con[parent]))
{
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void push(const T& val)// 模拟的就是堆的插入==尾插+向上调整
{
_con.push_back(val);
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];
}
bool empty()
{
return _con.empty();
}
size_t size()
{
return _con.size();
}
};
}
(2)Test.cpp
#include<algorithm>
#include"Queue.h"
void test_priority_queue_simulation()
{
yjl::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(2);
pq.push(5);
pq.push(4);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
int main()
{
test_priority_queue_simulation();
return 0;
}
好了,今天的分享就到这里了
如果对你有帮助,记得点赞👍+关注哦!
我的主页还有其他文章,欢迎学习指点。关注我,让我们一起学习,一起成长吧!
本文标签: 适配器容器stlpriorityqueue
版权声明:本文标题:【C++】---STL容器适配器之priority_queue 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728518995a1161855.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论