admin管理员组文章数量:1624345
「前言」
「归属专栏」C嘎嘎
「主页链接」个人主页
「笔者」枫叶先生(fy)
目录
一、priority_queue介绍
二、priority_queue使用
三、仿函数
四、priority_queue模拟实现
4.1 版本1
4.2 版本2
一、priority_queue介绍
priority_queue文档介绍
翻译：
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素
pop_back()：删除容器尾部元素
- （5）标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用 vector
- （6）需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数 make_heap、push_heap 和 pop_heap 来自动完成此操作
template <class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class priority_queue;优先级队列 priority_queue 默认使用的适配器是 vector（class Container = vector<T>），第三个模板参数是仿函数（class Compare = less<typename Container::value_type> ），仿函数下面解释
使用 priority_queue 要包含头文件 <queue>，与 queue 的头文件一致
#include <queue>注：priority_queue 的结构就是堆，即二叉树
二、priority_queue使用
成员函数介绍：
接口简单介绍，C++11先不介绍，后面再学
函数声明 接口说明 priority_queue() 构造一个空的优先级队列 priority_queue(first,last) 以迭代器区间构造一个优先级队列 empty( ) 检测优先级队列是否为空，是返回true，否则返回false top( ) 返回优先级队列中最大(最小元素)，即堆顶元素 push(x) 在优先级队列中插入元素x pop() 删除优先级队列中最大(最小)元素，即堆顶元素
优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority_queue
注意：默认情况下 priority_queue 是大堆（即降序）
优先级队列默认大的优先级高，传的是 less 仿函数，底层是一个大堆；如果想控制小的优先级高，需手动传 greater 仿函数，其底层是一个小堆
测试代码
#include <iostream>
#include <queue>
using namespace std;
void Test_priority_queue()
{
priority_queue<int> pq;
pq.push(3);
pq.push(6);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
int main()
{
Test_priority_queue();
return 0;
}运行结果，降序
如果要改成小堆（即升序），需要手动传第三个参数 greater ，使用 greater 需要包含头文件 <functional>
#include <functional> // greater的头文件要传第三个模板参数，就必须传第二个模板参数，这是使用缺省参的语法规定
priority_queue<int, greater<int>> pq; //error 正确使用如下
priority_queue<int, vector<int>, greater<int> > pq;#include <iostream>
#include <queue>
#include <functional>
using namespace std;
void Test_priority_queue()
{
priority_queue<int, vector<int>, greater<int> > pq;
pq.push(3);
pq.push(6);
pq.push(5);
pq.push(1);
pq.push(6);
pq.push(8);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
int main()
{
Test_priority_queue();
return 0;
}运行结果，升序
三、仿函数
仿函数是 STL 的六大组件之一
仿函数：使一个类的使用看上去像一个函数，该类定义出来的对象称为函数对象
仿函数的实现就是在类中重载 () 操作符，使得该类具备类似函数的行为，就是一个仿函数
测试，创建一个仿函数
namespace fy
{
class less
{
public:
bool operator()(int x, int y)
{
return x < y;
}
};
}
void Test()
{
fy::less lessCompare;
cout << lessCompare(10, 20) << endl;
}运行结果
仿函数支持泛型
namespace fy
{
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y)const
{
return x < y;
}
};
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y)const
{
return x > y;
}
};
}
void Test()
{
fy::less<int> lessCompare;
cout << lessCompare(10, 20) << endl;
fy::greater<double> greaterCompare;
cout << greaterCompare(10.0, 20.0) << endl;
}运行结果
这就是仿函数，实际上仿函数调用的只是重载的 operator() 而已
为什么要有仿函数？为了替代 C语言中的函数指针，使用代码更直观，函数指针使用起来头大，难理解！！
void( * set_malloc_handler(void (*f)()))() //这是函数指针.......所以，仿函数的出现就是为了替代 C语言的函数指针
四、priority_queue模拟实现
优先级队列的模拟实现也是很简单，因为它是容器适配器，可以使用已有的生成我们想要的
4.1 版本1
这里要注意的向上调整和向下调整的写法，数据结构已经学过，就不废话了。这个版本的缺陷是不能很好的支持升序和降序，只能是其中的一种，使用改升序或降序就必须修改源代码，修改后也是两者不能兼并，极其不好，版本2 则是使用仿函数，可以使两者可以同时兼并
priority_queue.h
#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace fy //防止命名冲突
{
//优先级队列模拟实现
template<class T, class Container = vector<T>>
class priority_queue
{
public:
priority_queue(){}
//迭代器区间构造
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
//堆的向上调整
void adjust_up(size_t child)
{
size_t parent = (child - 1) / 2;
while (child > 0)
{
if (_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);
adjust_up(_con.size() - 1);
}
//堆的向下调整
void adjust_down(size_t parent)
{
size_t child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && _con[child] < _con[child + 1])
{
child++;
}
if (_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();
adjust_down(0);
}
//获取堆顶元素
const T& top()const
{
return _con[0];
}
bool empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
Container _con;
};
}
Test.cpp
#include "PriorityQueue.h"
void Test_priority_queue()
{
fy::priority_queue<int> pq;
pq.push(5);
pq.push(1);
pq.push(9);
pq.push(6);
pq.push(3);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
int main()
{
Test_priority_queue();
return 0;
}运行结果
4.2 版本2
priority_queue.h
#pragma once
#include <iostream>
#include <vector>
using namespace std;
namespace fy //防止命名冲突
{
//比较方式 < --- 使其结构形成大堆
template<class T>
class less
{
public:
bool operator()(const T& x, const T& y) const
{
return x < y;
}
};
//比较方式 > --- 使其结构形成小堆
template<class T>
class greater
{
public:
bool operator()(const T& x, const T& y) const
{
return x > y;
}
};
//优先级队列模拟实现
template<class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
public:
priority_queue(){}
//迭代器区间构造
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:_con(first, last)
{
for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
{
adjust_down(i);
}
}
//堆的向上调整
void adjust_up(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);
adjust_up(_con.size() - 1);
}
//堆的向下调整
void adjust_down(size_t parent)
{
Compare com;
size_t child = parent * 2 + 1;
while (child < _con.size())
{
//if (child + 1 < _con.size() && _con[child] < _con[child + 1])
if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
{
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();
adjust_down(0);
}
//获取堆顶元素
const T& top()const
{
return _con[0];
}
bool empty()const
{
return _con.empty();
}
size_t size()const
{
return _con.size();
}
private:
Container _con;
};
}Test.cpp
#include "PriorityQueue.h"
void Test_priority_queue()
{
//默认是大堆 less
fy::priority_queue<int> pq;
pq.push(5);
pq.push(1);
pq.push(9);
pq.push(6);
pq.push(3);
pq.push(3);
while (!pq.empty())
{
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
int arr[] = { 5,1,9,6,3,3 };
//默认是大堆 less
fy::priority_queue<int> pq2(arr, arr+6);
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
//小堆, greater
fy::priority_queue<int, vector<int>, greater<int> > pq3(arr, arr + 6);
while (!pq3.empty())
{
cout << pq3.top() << " ";
pq3.pop();
}
cout << endl;
}
int main()
{
Test_priority_queue();
return 0;
}--------------------- END ----------------------
「 作者 」 枫叶先生
「 更新 」 2023.2.11
「 声明 」 余之才疏学浅，故所撰文疏漏难免，
或有谬误或不准确之处，敬请读者批评指正。本文标签： 优先级队列初阶stlpriorityqueue
版权声明：本文标题：【C++初阶】十一、STL---priority_queue（优先级队列） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://m.elefans.com/xitong/1728894758a1178267.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论