C++ STL 优先队列 (priority_queue)

std::priority_queue

<queue>

优先队列

  1、第一个元素始终为最大元素。

  2、有着类似于堆的特性，它可以在其中随时插入元素。

  3、支持下标访问（随机访问迭代器）

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

• empty( )

• size( )

• front( )

• push_back( )

• pop_back( )

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

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

成员函数

注：
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、小根堆

（1）输入输出

#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;
}

（2）利用swap高效地清空队列

void clear( priority_queue<int> &pq ) {
    priority_queue<int> empty;
    pq.swap ( empty );
}

（3）利用=高效地清空队列

void clear( priority_queue<int> &pq ) {
    priority_queue<int> t;
    pq = t;
}