C++ STL 优先队列 (priority

`std::priority_queue`

<queue>

优先队列

优先队列是一种容器适配器，根据某些严格的弱排序标准，使其第一个元素始终包含的最大元素。

这种特性类似于堆，它可以在其中随时插入元素，并且只能检索最大堆元素（即优先级队列顶部的元素）。

优先队列内部的实现需要依赖基础容器，该容器应可通过随机访问[i]和迭代器Iterator访问，并需要支持以下操作

empty( )
size( )
front( )
push_back( )
pop_back( )

显而易见的是有deque和vector这两个基础容器支持以上操作

所以在默认情况下，如果未为priority_queue指定基础容器类，则将使用vector。

成员函数

(constructor)	Construct priority queue (public member function )
empty	优先队列是否为空
size	返回优先队列的当前元素个数
top	访问顶部元素（返回顶部元素的常量引用）
push	插入一个元素
pop	删除顶部元素
emplace	构造并插入一个元素
void swap (priority_queue& x)	交换两个队列的内容

注：

1、emplace 与 push 相比更加优化了对内存空间的使用，具体可以另行查询

2、swap 是交换两个同一类型的优先队列内的所有元素，如 a.swap ( x ) 即交换队列 a 和 x 的所有元素

构造优先队列

        <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

注意：大根堆为less，小根堆为greater。

函数成员用例

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;

}

巴特西

C++ STL 优先队列 (priority_queue)