优先队列

定义

优先队列是一种特殊的队列，它是以堆的形式来存储队列中的元素，并且每次在插入和删除数据时，会自动对数据进行排序，相当于大顶堆序。

优先队列priority_queue在c++中在queue头文件中，能够在$O(1)$的时间内找到最大的元素（默认为大顶堆），并且能在在$O(logn)$的时间内插入和删除元素。

常用函数

priority_queue<int> q;
q.top();//取队列首元素，也就是堆顶元素
q.empty();//判断队列是否为空
q.size();//返回队列的元素个数
q.push(1);//向优先队列中插入一个元素
q.pop();//弹出队列头元素

基本数据类型的优先队列

c++ 中优先队列默认是大顶堆序，如果我们想将优先队列变成小顶堆序，需要在定义优先队列是作出相应的调整：

priority_queue<int> q_default;//默认是大顶堆序
priority_queue<int,vector<int>,less<int> >q;//大顶堆
priority_queue<int,vector<int>,greater<int> > q2;//小顶堆

int main()
{
    int arr[10] = {1,3,5,7,9,2,4,6,8,10};
    //  优先队列默认是从大到小排序，执行如下程序，可以得到
    //  10 9 8 7 6 5 4 3 2 1
    //  也可以写成 priority_queue<int,vector<int>,less<int> >
    //  最后两个> 需要添加空格，否则会视为逻辑右移。
    priority_queue<int> q1;
    for(int i = 0 ; i < 10 ; i ++)
        q1.push(arr[i]);
    while(!q1.empty())
        printf("%d ",q1.top()),q1.pop();
    puts("\n");

    //  如果我们想让从小到大排序,输出1 2 3 4 5 6 7 8 9 10
    priority_queue<int,vector<int>,greater<int> > q2;
    for(int i = 0 ; i < 10 ; i ++)
        q2.push(arr[i]);
    while(!q2.empty())
        printf("%d ",q2.top()),q2.pop();
    puts("\n");
    return 0;
}

其他结构体的优先队列

优先队列会对不同结构体进行比较排序，这就使得如果我们使用优先队列存储结构体的时候，必须提供相应的比较方法。这里主要有两种方法：运算符重载和自定义比较函数。

运算符重载

如果对结构体进行了运算符重载，那么这个结构体也可以使用sort函数对其进行排序。

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct node{
    int x,y;

    node(){}
    node(int x,int y):x(x),y(y){}
    //  这里x代表当前结构体的x,a.x代表传进来的结构体的x
    //  运算符重载主要是为了让数据类型为node的容器可以进行排序,排序的时候使用<进行两个元素的比较
    //  return x < a.x 时，代表x越小的node在node数组排序时在前面。
    //  return x > a.x 时，代表x越大的node在node数组排序时在前面。
    bool operator< (const node &a)const {
        return x < a.x;
    }
};
int main()
{
    vector<node> nodeList(5);
    nodeList[0] = node(1,3);
    nodeList[1] = node(2,4);
    nodeList[2] = node(2,5);
    nodeList[3] = node(3,4);
    nodeList[4] = node(5,5);
    //  使用nodeList的运算符重载比较函数,node.x越小越在前。
    sort(nodeList.begin(),nodeList.end());
    for(int i = 0 ; i < 5 ; i ++)
        printf("%d %d\n",nodeList[i].x,nodeList[i].y);
    puts("\n");
    priority_queue<node> q3;
    //  现在我们考虑传入的参数是结构体的时候，由于结构体没有默认比较函数，所以我们需要给结构体定义一些比较函数
    //  1.假设运算符重载后，node.x 越小的节点在排序时次序越靠前，那么由于优先队列默认是大顶堆的，那么执行如下代码输出，和sort函数是完全相反的顺序
    //    5 5
    //    3 4
    //    2 4
    //    2 5
    //    1 3
    for(int i = 0 ; i < 5 ; i ++)
        q3.push(nodeList[i]);
    while(!q3.empty())
        printf("%d %d\n",q3.top().x,q3.top().y),q3.pop();
    puts("\n");
    return 0;
}

自定义比较

我们之前如果想对结构体进行排序，我们往往会写如下的函数：

//  按照node.x从大到小排序
bool cmp2(const node &a ,const node &b)
{
    return a.x > b.x;
}
//  按照node.x从大到小排序，如果二者相同，那么按照node.y 从大到小排序
bool cmp3(const node &a,const node &b)
{
    return (a.x == b.x)?(a.y > b.y):(a.x > b.x);
}

但是在优先队列中，我们需要稍微改变一下，然后在定义优先队列的时候加上另外两个参数。

priority_queue<node,vector<node>,cmp > q4;

struct cmp
{
    bool operator()(const node &a,const node &b)
    {
        return a.x > b.x;
    }
};

#include <algorithm>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct node{
    int x,y;
    node(){}
    node(int x,int y):x(x),y(y){}
    bool operator< (const node &a)const {
        return x < a.x;
    }
};

struct cmp
{
    bool operator()(const node &a,const node &b)
    {
        return a.x > b.x;
    }
};
int main()
{
    vector<node> nodeList(5);
    nodeList[0] = node(1,3);
    nodeList[1] = node(2,4);
    nodeList[2] = node(2,5);
    nodeList[3] = node(3,4);
    nodeList[4] = node(5,5);

    priority_queue<node,vector<node>,cmp > q4;
    for(int i = 0 ; i < 5 ; i ++)
        q4.push(nodeList[i]);
    while(!q4.empty())
        printf("%d %d\n",q4.top().x,q4.top().y),q4.pop();
    puts("\n");
    return 0;
}

更多运算符重载实例

struct node{
    int x,y;

    node(){}
    node(int x,int y):x(x),y(y){}
    //  这里x代表当前结构体的x,a.x代表传进来的结构体的x
    //  运算符重载主要是为了让数据类型为node的容器可以进行排序,排序的时候使用<进行两个元素的比较
    //  return x < a.x 时，代表x越小的node在node数组排序时在前面。
    //  return x > a.x 时，代表x越大的node在node数组排序时在前面。
    bool operator< (const node &a)const {
        return x < a.x;
    }
    //  写了如下函数后，可以直接比较nodeA == nodeB
    bool operator== (const node &a)const{
        return x == a.x && y == a.y;
    }
    //  写了如下函数后，可以直接比较nodeA = nodeB
    bool operator!= (const node &a)const{
        return x != a.x || y != a.y;
    }
    //  写了如下函数后，可以直接用nodeA + nodeB生成一个新的node
    node operator+ (const node &a)const {
        return node(x + a.x,y+a.y);
    }
};