优先队列详解

悠悠 2022-08-01 11:22 273阅读 0赞

优先队列是一种容器适配器（容器适配器的概念本人不会解释，故此处无法作出说明），它的第一个元素（位于头部top）总是队列中最大的元素，这里的“最大”是指队列元素的严格弱序中的“最大”。严格弱序是一系列数或事物按照一定的比较关系“<”排列得出的序列，“<”可以是数学中进行数值比较的大于，也可以是小于，还可以是其它含义，这大概与离散数学中的“偏序关系”相仿。

在内存充足的情况下，优先队列能被无限地插入元素。

优先队列作为一个容器适配器，它使用其它容器作为底层容器，并提供一系列访问元素的函数。优先队列中的元素从底层容器的“尾部（back）”弹出，即是从队列的顶部（top）弹出。底层容器需要满足的条件是可以通过迭代器随机访问其中的元素并且支持以下的操作：

*  front()
 *  push\_back()
 *  pop\_back()

故此，容器vector和deque可以作为底层容器，在创建优先队列时若没有声明使用何种容器，则默认使用vector。

创建一个优先队列的格式：

priority\_queue<T, Container, Compare>

可以看出，创建一个优先队列默认需要三个参数（实际应用上有些参数可以省去）。参数解释：

**T：**队列中元素的数据类型

**Container****:** 用于储存和访问队列元素的底层容器的类型。

**Compare****:** 比较关系，默认是数值上的小于关系，比如1<2,6<7，此时队列中元素由队头到队由大到小排列，采用默认compare时此参数可以省去。当需要采用其它标准进行比较时需要额外定义这一比较方式（下例示）。当满足比较关系”<”时，返回true，否则返回false。

创建优先队列的一个例子：

#include <iostream>
    #include <queue>
    using namespace std;
    
    class cmp
    {
    public:
       bool operator() (const int a,const int b)
       {
           return a>b;
       }
    };
    
    int main()
    {
        priority_queue<int,vector<int>,cmp>que1;
        priority_queue<int,vector<int> >que2;
        int a[]={1,3,4,2,5,0,6};
        for(int i=0;i<7;i++)
        {
            que1.push(a[i]);
            que2.push(a[i]);
    }
        cout<<"que1:";
        while(!que1.empty())
        {
            cout<<que1.top()<<" ";
            que1.pop();
        }
        cout<<endl<<"que2:";
        while(!que2.empty())
        {
            cout<<que2.top()<<" ";
            que2.pop();
        }
        return 0;
    }

输出结果：

que1:0 1 2 3 4 5 6

que2:6 5 4 3 2 1 0

上例中que1使用比较方式cmp类，队列中元素由小到大排列，而que2使用默认形式的“<”，元素按照优先级排列，队头元素最大。

优先队列成员函数（除构造函数、析构函数）简介：

（1）priority\_queue::empty

判断队列是否为空（也即是size是否为0），是则返回true，否则返回false。优先队列的此成员函数实际上调用底层容器的同名函数。

（2）priority\_queue::size

返回队列中元素的个数。此函数实际上调用底层容器的同名函数。这个函数也可以用于判断队列是否为空。

（3）priority\_queue::top

返回队头元素的常引用，队头元素是在所设定的比较关系下最大也即优先级最高的元素。此函数实际上调用底层容器的front函数。

（4）priority\_queue::pop

清除队头元素。

（5）priority\_queue::push

给队列插入元素，新元素会按其优先级被排列到适当位置。

注：对于自定义类型比如结构体，必须重载<才能进行比较。见下例：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <queue>
    using namespace std;
    
    class Node
    {
    public:
        int idx;
        static int cnt;
        Node()
        {
            idx=cnt++;
        }
    }a[10];
    
    int Node::cnt=1;
    
    bool operator < (Node a,Node b)
    {
        return a.idx>b.idx;
    }
    
    int main()
    {
    //省略container和compare参数，此时container默认使用vector，而compare默认使用<，而<已经重载，于是可以按照自定义方式比较。
        priority_queue<Node>que;//省略container和compare参数
        for(int i=0;i<10;i++)
            que.push(a[i]);
        while(!que.empty())
        {
            cout<<que.top().idx<<" ";
            que.pop();
        }
        return 0;
    }

结果：1 2 3 4 5 6 7 8 9 10

若将上述重载<函数中的return a.idx>b.idx;改为return a.idx<b.idx;则输出：10 9 8 7 6 5 4 3 2 1

可以看出，利用自定义compare可以使得优先队列按照某些所需要的规则排序。

[ContractedBlock.gif]: http://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20220731/3d40355c93554e10bfffa6510a0a8b62.png