33、STL中的priority_queue的实现
2021/7/28 23:10:57
本文主要是介绍33、STL中的priority_queue的实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
priority_queue,优先队列,是一个拥有权值观念的queue,它跟queue一样是顶部入口,底部出口,在插 入元素时,元素并非按照插入次序排列,它会自动根据权值(通常是元素的实值)排列,权值最高,排 在最前面,如下图所示。
默认情况下,priority_queue使用一个max-heap完成,底层容器使用的是一般为vector为底层容器,堆heap 为处理规则来管理底层容器实现 。priority_queue的这种实现机制导致其不被归为容器,而是一种容器配 接器。关键的源码如下:
template <class T, class Squence = vector<T>, class Compare = less<typename Sequence::value_tyoe> > class priority_queue{ ... protected: Sequence c; // 底层容器 Compare comp; // 元素大小比较标准 public: bool empty() const {return c.empty();} size_type size() const {return c.size();} const_reference top() const {return c.front()} void push(const value_type& x) { c.push_heap(x); push_heap(c.begin(), c.end(),comp); } void pop() { pop_heap(c.begin(), c.end(),comp); c.pop_back(); } };
priority_queue的所有元素,进出都有一定的规则,只有queue顶端的元素(权值最高者),才有机会被外 界取用,它没有遍历功能,也不提供迭代器
举个例子:
#include <queue> #include <iostream> using namespace std; int main() { int ia[9] = {0,4,1,2,3,6,5,8,7 }; priority_queue<int> pq(ia, ia + 9); cout << pq.size() <<endl; // 9 for(int i = 0; i < pq.size(); i++) { cout << pq.top() << " "; // 8 8 8 8 8 8 8 8 8 } cout << endl; while (!pq.empty()) { cout << pq.top() << ' ';// 8 7 6 5 4 3 2 1 0 pq.pop(); } return 0; }
这篇关于33、STL中的priority_queue的实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-27[开源] 一款轻量级的kafka可视化管理平台
- 2024-10-23Kafka消息丢失资料详解:初学者必看教程
- 2024-10-23Kafka资料新手入门指南
- 2024-10-23Kafka解耦入门:新手必读教程
- 2024-10-23Kafka入门:新手必读的简单教程
- 2024-10-23Kafka入门:新手必读的简单教程
- 2024-10-23Kafka消息丢失入门:新手必读指南
- 2024-10-23Kafka消息队列入门:新手必看的简单教程
- 2024-10-23Kafka消息队列入门与应用
- 2024-10-23Kafka重复消费入门:轻松掌握Kafka重复消息处理技巧