std::priority_queue
<queue>
优先队列
优先队列是一种容器适配器,根据某些严格的弱排序标准,使其第一个元素始终包含的最大元素。
这种特性类似于堆,它可以在其中随时插入元素,并且只能检索最大堆元素(即优先级队列顶部的元素)。
优先队列内部的实现需要依赖基础容器
,该容器应可通过随机访问[i]
和迭代器Iterator
访问,并需要支持以下操作
empty( )
size( )
front( )
push_back( )
pop_back( )
显而易见的是有deque
和vector
这两个基础容器支持以上操作
所以在默认情况下,如果未为priority_queue
指定基础容器类,则将使用vector
。
成员函数
构造优先队列
<queue>
/* 1 */ priority_queue<int> pq1; //默认大根堆且默认基础容器为vector
/* 2 */ priority_queue<vector<int>, less<int> > pq2; //与 1 的性质一模一样
/* 3 */ priority_queue<deque<int>, greater<int> > pq3; //小根堆且基础容器为deque
函数成员用例
1、push、top、empty、pop、大根堆
(1)int
#include <iostream>
#include <queue>
using namespace std;
int main ( void )
{
priority_queue<int> pq; //大根堆,默认降序(大的在前,小的在后)
pq.push ( 60 );
pq.push ( 20 );
pq.push ( 40 );
pq.push ( 1 );
pq.push ( 25 );
while ( !pq.empty() ) // pq不为空则循环
{
cout << pq.top() << " "; //添加新元素
pq.pop(); //弹出头元素
}
return 0;
}
(2)string
#include <iostream>
#include <queue>
using namespace std;
int main ( void )
{
priority_queue<string> pq; //大根堆,默认降序(大的在前,小的在后)
pq.push ( "abc" );
pq.push ( "abd" );
pq.push ( "acd" );
pq.push ( "cda" );
pq.push ( "abcd" );
while ( !pq.empty() ) // pq不为空则循环
{
cout << pq.top() << endl; //添加新元素
pq.pop(); //弹出头元素
}
return 0;
}
2、swap、emplace、小根堆
#include <iostream>
#include <queue>
using namespace std;
int main ( void )
{
priority_queue<int, vector<int>, greater<int> > pq1; //小根堆,默认降序(小的在前,大的在后)
pq1.emplace ( 5 );
pq1.emplace ( 4 );
pq1.emplace ( 3 );
pq1.emplace ( 2 );
pq1.emplace ( 1 );
priority_queue<int, vector<int>, greater<int> > pq2;
pq2.emplace ( 5 * 2 );
pq2.emplace ( 4 * 2 );
pq2.emplace ( 3 * 2 );
pq2.emplace ( 2 * 2 );
pq2.emplace ( 1 * 2 );
cout << "pq1:" << endl;
while ( !pq1.empty() ) // pq不为空则循环
{
cout << pq1.top() << " "; //添加新元素
pq1.pop(); //弹出头元素
}
cout << endl << "pq2:" << endl;
while ( !pq2.empty() ) // pq不为空则循环
{
cout << pq2.top() << " "; //添加新元素
pq2.pop(); //弹出头元素
}
cout << endl;
return 0;
}