C/C++ | STL | std::priority_queue for Max and Min Heap
最编程
2024-08-14 20:29:09
...
优先队列 priority_queue
优先队列是容器适配器的一种类型,特别设计为它的第一个元素总是它包含的元素中最大的元素,根据一些严格的弱顺序标准。
这个上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先级队列顶部的元素)。
优先级队列被实现为容器适配器,这些适配器类使用特定容器类的封装对象作为其底层容器,提供一组特定的成员函数来访问其元素。元素从特定容器的“后面”弹出,该容器称为优先级队列的顶部。
底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应通过随机访问迭代器访问,并支持以下操作:
- empty() 如果优先队列为空,则返回真
- pop() 删除第一个元素
- push() 加入一个元素
- size() 返回优先队列中拥有的元素的个数
- top() 返回优先队列中有最高优先级的元素
标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用标准容器向量。
任何时候都需要支持随机访问迭代器,以便在内部保持堆结构。这是由容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成的。
大顶堆:
priority_queue<int> q;
for( int i= 0; i< 10; ++i ) q.push(i);
while( !q.empty() ){
cout<<q.top()<<endl;
q.pop();
}
小顶堆
priority_queue<int, vector<int>, greater<int> > q;
for( int i= 0; i< 10; ++i ) q.push(10-i);
while( !q.empty() ){
cout << q.top() << endl;
q.pop();
}
推荐阅读
-
C语言内存管理的重要性
-
"解析 C 标准库的功能和特点"
-
C++实现:视频教程演示YUV420与RGB相互转换(第二部分)
-
OpenCV-based Object Tracking in C++/Python (使用C++/Python进行基于OpenCV的目标追踪)
-
KCF代码运行并显示效果(C++)
-
使用opencv3和C++编程语言实现简单目标跟踪的Tracker
-
在线代码执行工具(支持PHP,Java,C++等语言)-访问 http://www.it1352.com/Onlinetools
-
C/C++多线程:参数传递的方法
-
《c语言程序设计a》在线作业 - 16秋华师华师c语言作业
-
在线转换Java代码为C#代码