优先队列

队列是先进先出的一种逻辑数据结构，优先队列是可以按照指定顺序输出元素的一种队列。它的底层实现是堆（堆的底层实现是用一个数组来模拟一棵树，在面试中可能会让你在白板上写堆的底层实现）。

在c++中，已经定义好了优先队列的容器类，我们可以直接调用。

#include <queue>;

priority_queue<int> pq;
pq.push(num);

我们可以以下代码来进行测试：

#include <iostream>
#include <queue>
#include <ctime>

using namespace std;


int main() {
    srand(time(NULL));//种子
    
    priority_queue<int> pq;
    for(int i = 0; i < 10; i ++)
    {
        int num = rand()%100;
        pq.push(num);
        cout<<"insert "<<num <<" in priority queue."<<endl;
    }
    while(!pq.empty())
    {
        cout<<pq.top()<<" ";
        pq.pop();
    }
    return 0;
}

上面这段代码就是随机生成一些树，存入优先队列，然后再输出。通过输出的结果可以发现，c++默认的输出顺序是从大到小，即底层是以最大堆实现的。

图1.1 优先队列的输出

如果想以从小到大的顺序输出，那该怎么办呢？

在c++中，我们在定义优先堆列的时候，需要多传入几个参数。

priority_queue<int, vector<int>, greater<int>> pq2;

第一个参数是存入的数据类型，第二个参数是底层的结构实现，通常情况下，我们的顶层实现都是以vector向量来实现，第三个参数是c++帮我们定义好的比较函数。默认情况下是less。
可以通过测试发现，输出的元素是从小到大的顺序。

通常情况下，我们使用最小堆和最大堆就可以解决大多数的问题了。

但在一些极特别的情况下，我们需要自定义大小的关系。这种情况下怎么办呢？

在c++中，我们可以使用自定义的comparator的priority queue来实现。

bool myCmp(int a, int b)  
{
      return a%10 <b%10; //比较个位数谁小
}

priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCmp);

通过测试可以看到输出的元素顺序。

至此，是优先队列的输出顺序定义，下面贴出上述三种情况的定义／测试的完成代码。

#include <iostream>
#include <queue>
#include <ctime>

using namespace std;

bool myCmp( int a , int b ){

    return a%10 > b%10;
}

int main() {

    srand(time(NULL));

    // 默认的priority queue, 底层是最大堆
    priority_queue<int> pq;

    for( int i = 0 ; i < 10 ; i ++){
        int num = rand()%100;
        pq.push( num );
        cout<<"insert "<<num<<" in priority queue."<<endl;
    }

    while( !pq.empty() ){
        cout<<pq.top()<<" ";
        pq.pop();
    }

    cout<<endl<<endl;

    // 使用greater的priority queue, 底层是最小堆
    priority_queue<int, vector<int>, greater<int>> pq2;

    for( int i = 0 ; i < 10 ; i ++){
        int num = rand()%100;
        pq2.push( num );
        cout<<"insert "<<num<<" in priority queue."<<endl;
    }

    while( !pq2.empty() ){
        cout<<pq2.top()<<" ";
        pq2.pop();
    }

    cout<<endl<<endl;

    // 使用自定义Comparator的priority queue
    priority_queue<int, vector<int>, function<bool(int,int)>> pq3(myCmp);

    for( int i = 0 ; i < 10 ; i ++){
        int num = rand()%100;
        pq3.push( num );
        cout<<"insert "<<num<<" in priority queue."<<endl;
    }

    while( !pq3.empty() ){
        cout<<pq3.top()<<" ";
        pq3.pop();
    }

    return 0;
}