美文网首页
优先队列

优先队列

作者: 什锦甜 | 来源:发表于2018-06-05 16:07 被阅读35次

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

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

    相关文章

      网友评论

          本文标题:优先队列

          本文链接:https://www.haomeiwen.com/subject/sotmsftx.html