admin管理员组文章数量:1624350
目录
priority_queue的使用:
priority_queue的默认定义的模板:
priority_queue的定义并初始化:
priority_queue的模拟实现:
堆的排序算法:
堆的向上调整算法核心:
堆的向下调整算法核心:
priortiy_queue接口的模拟实现
priority_queue的使用:
priority_queue文档介绍
priority_queue是一个拥有权值观念的queue,它允许加入新元素、移除旧元素、审视旧元素等功能,由于其是一个queue,所以只允许在底端插入元素,并从顶端取出元素,除此之外别无其它存取元素的途径。 优先级队列默认使用vector 作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:默认情况下priority_queue是大堆。priority_queue的默认定义的模板:
注意:
- 默认情况下priority_queue是大堆。
- 默认情况下priority_queue是以vector作为底层容器
(大多数情况下都是使用vector作为底层容器即可,我们需要变动的只是存储类型、构造堆结构的形式)
方式一:规定的存储类型,默认内部构造大堆结构
//int类型:
priority_queue<int> q1;
//double类型
priority_queue<double> q2;
方式二:默认内部构造小堆结构
priority_queue<int, vector<int>, greater<int>> q;
priority_queue的定义并初始化:
template <class InputIterator> priority_queue (InputIterator first, InputIterator last, const Compare& comp = Compare(), const Container& ctnr = Container());
vector<int> v{ 1,2,3,4,5,6,7,8,9,10 };
//使用大堆结构
priority_queue<int> q1(v.begin(), v.end());
//使用小堆结构
priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
empty | 测试容器是否为空(公共成员函数) |
size | 返回大小(公共成员函数) |
top | 访问顶部元素(公共成员功能) |
push | 插入元素(公共成员函数) |
emplace | (C++11)构造并插入元素(公共成员函数) |
pop | 删除顶部元素(公共成员函数) |
swap | (C++11)交换内容(公共成员函数) |
#include<iostream>
#include<queue>
#include<list>
using namespace std;
int main() {
priority_queue<int> q1;
for (int i = 0; i < 10; i++)
{
q1.push(i);
}
//q1:9 8 5 6 7 1 4 0 3 2
vector<int> v{ 10,20,30 };
priority_queue<int> q2(v.begin(), v.end());
//q2:30 20 10
q2.swap(q1);
cout << q1.size() << endl;//输出:3
cout << q2.size() << endl;//输出:10
//q1:30 20 10
//q2:9 8 5 6 7 1 4 0 3 2
while (!q1.empty()) {
cout << q1.top() << " ";
q1.pop();
}
cout << endl;
//输出:30 20 10
return 0;
}
priority_queue的模拟实现:
注意,下标计算父子间的关系:
- leftchild = parent * 2 + 1
- rightchild = parent * 2 + 2
- parent = (child - 1) / 2 (因为只会保留整数部分)
堆的排序算法:
此处以小根堆为例;(向上调整算法用于存入数据)。
堆的向上调整算法核心:
(父节点与子节点大小的比较,子对父)
- 如果比父亲小,则交换,然后继续向上比较并调整(最多调整到跟节点就结束了)。
- 如果比父亲大,则调整结束。
堆的向下调整算法核心:
(父节点与子节点大小的比较,父对子)
- 如果比父亲小,则交换,然后继续向下比较并调整。(最多调整到叶子节点就结束了)
- 如果比父亲大,则调整结束。
本人的堆的算法博客:
- 【C语言】-- 数据结构 -- 堆的实现(小堆)
- 【C语言】-- 数据结构 -- 利用堆排序【具体函数实现】
priortiy_queue接口的模拟实现
只要知道了堆的向上排序调整算法和向下排序调整算法后,其实prirotiy_queue的模拟实现几乎已经可以说是完成了。
成员函数 | 实现方法 |
push | 利用容量适配器本身的push_back(),并结合堆的向上调整算法。 |
pop | 根据堆的排序思维,利用swap(),将第一个元素与最后一个元素交换位子(确保中间元素的堆序不被打乱),然后容量适配器本身的pop_back(),再使用堆的向下调整算法。 |
top | 利用容量适配器本身的front() |
size | 利用容量适配器本身的size() |
empty | 利用容量适配器本身的empty() |
难度提升:
priortiy_queue是可以通过容量适配器实现less与gtreater实现,内部堆排序的结构不同。既然需要less与greater,我们也模拟实现一下。
template<class T, class Container = std::vector<T>, class Compare = less<T>>
template<class T>
class less { bool operator()(T& e1, T& e2) { return e1 < e2; } };
template<class T>
class greater { bool operator()(T& e1, T& e2) { return e1 > e2; } };
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
namespace qcr{
template<class T>
class less { bool operator()(T& e1, T& e2) { return e1 < e2; } };
template<class T>
class greater { bool operator()(T& e1, T& e2) { return e1 > e2; } };
template<class T, class Container = std::vector<T>, class Compare = less<T>>
class priority_queue {
public:
priority_queue():_con() {}
template<class InputIterator>
priority_queue(InputIterator begin, InputIterator end) : _con(begin, end) {
//数据的输入
//while (begin != end) {
// _con.push_back(*begin);
// ++begin;
//}
//数据的大小堆建立
for (int i = (_con.size() - 1 - 1) >> 1; i >= 0; --i)
Adjust_down(i);
}
void Pop() {
assert(!empty());
swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
Adjust_down(0);
}
bool empty()const {
return _con.empty();
}
size_t size()const {
return _con.size();
}
void push(T x) {
_con.push_back(x);
Adjust_up(_con.size() - 1);
}
const T& top()const
{
return _con.front();
}
//向下排序
void Adjust_down(size_t parent) {
size_t child = parent * 2 + 1;
while (child < _con.size()) {
if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))
++child;
if (Compare()(_con[parent], _con[child])) {
//将父节点子节点进行调换
std::swap(_con[parent], _con[child]);
//更新父、子节点的位置
parent = child;
child = parent * 2 + 1;
}
else{
//堆已经建立成功
break;
}
}
}
//向上排序
void Adjust_up(size_t child) {
size_t parent = (child - 1) >> 1;
while (child) {
if (Compare()(_con[parent], _con[child])) {
//将父节点子节点进行调换
std::swap(_con[parent], _con[child]);
//更新父、子节点的位置
child = parent;
parent = (child - 1) >> 1;
}
else {
//堆已经建立成功
break;
}
}
}
Container _con;
};
}
本文标签: 底层原理stlpriorityqueue
版权声明:本文标题:【C++ STL】-- priority_queue底层原理、使用、模拟实现 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728895021a1178298.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论