C++如何使用标准模板库(STL)中的优先队列?用法解析

2021年4月3日19:19:56 发表评论 1,309 次浏览

优先队列是一种容器适配器, 经过专门设计, 使得队列中的第一个元素是队列中所有元素中最大的, 并且元素的顺序不递增(因此, 我们可以看到队列中的每个元素都具有优先级{固定顺序})。

// Note that by default C++ creates a max-heap
// for priority queue
#include <iostream>
#include <queue>
  
using namespace std;
  
void showpq(priority_queue < int > gq)
{
     priority_queue < int > g = gq;
     while (!g.empty())
     {
         cout << '\t' << g.top();
         g.pop();
     }
     cout << '\n' ;
}
  
int main ()
{
     priority_queue < int > gquiz;
     gquiz.push(10);
     gquiz.push(30);
     gquiz.push(20);
     gquiz.push(5);
     gquiz.push(1);
  
     cout << "The priority queue gquiz is : " ;
     showpq(gquiz);
  
     cout << "\ngquiz.size() : " << gquiz.size();
     cout << "\ngquiz.top() : " << gquiz.top();
  
  
     cout << "\ngquiz.pop() : " ;
     gquiz.pop();
     showpq(gquiz);
  
     return 0;
}

输出如下:

The priority queue gquiz is :     30    20    10    5    1

gquiz.size() : 5
gquiz.top() : 30
gquiz.pop() :     20    10    5    1

如何为优先队列创建最小堆?

C++为此提供了以下语法。

//为优先队列创建最小堆的语法priority_queue <int, vector <int>, Greater <int >> g = gq;

// C++ program to demonstrate min heap
#include <iostream>
#include <queue>
  
using namespace std;
  
void showpq(priority_queue < int , vector< int >, greater< int >> gq)
{
     priority_queue < int , vector< int >, greater< int >> g = gq;
     while (!g.empty())
     {
         cout << '\t' << g.top();
         g.pop();
     }
     cout << '\n' ;
}
  
int main ()
{
     priority_queue < int , vector< int >, greater< int >> gquiz;
     gquiz.push(10);
     gquiz.push(30);
     gquiz.push(20);
     gquiz.push(5);
     gquiz.push(1);
  
     cout << "The priority queue gquiz is : " ;
     showpq(gquiz);
  
     cout << "\ngquiz.size() : " << gquiz.size();
     cout << "\ngquiz.top() : " << gquiz.top();
  
  
     cout << "\ngquiz.pop() : " ;
     gquiz.pop();
     showpq(gquiz);
  
     return 0;
}

输出如下:

The priority queue gquiz is :     1    5    10    20    30

gquiz.size() : 5
gquiz.top() : 1
gquiz.pop() :     5    10    20    30

注意 :上面的语法很难记住, 因此在使用数字值的情况下, 我们可以将值乘以-1并使用最大堆来获得最小堆的效果

优先队列的方法有:

  • C++ STL中的priority_queue::empty()–空()函数返回队列是否为空。
  • C++ STL中的priority_queue::size()–尺寸()函数返回队列的大小。
  • C++ STL中的priority_queue::top()–返回对队列最顶部元素的引用
  • C++ STL中的priority_queue::push()–推(g)函数在队列末尾添加元素" g"。
  • C++ STL中的priority_queue::pop()–pop()函数删除队列的第一个元素。
  • C++ STL中的priority_queue::swap()–此功能用于将一个优先队列的内容与相同类型和大小的另一优先队列的内容交换。
  • C++ STL中的priority_queue::emplace()–此功能用于将新元素插入优先队列容器, 新元素将添加到优先队列的顶部。
  • C++ STL中的priority_queue value_type–表示存储为priority_queue中的元素的对象的类型。它充当模板参数的同义词。

STL中有关优先队列的最新文章

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。

被认为是行业中最受欢迎的技能之一, 我们拥有自己的编码基础C++ STL通过激烈的问题解决过程来训练和掌握这些概念。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: