C语言-优先队列(priority queue)详解

0x00、优先队列(priority queue)

priority queue是一个用"堆"实现的，类似set的容器，有着queue的基本功能。特征是"具有优先级，可以按照优先级出队"

可能不是特别好理解，其实就是一个排序啦。。。

举个栗子：

3入队，4入队，1入队，如果是queue的容器，出队顺序为3,4,1，而priority queue则在内部会排好序，出队顺序为4,3,1。

这种数据结构在解决一些高级问题，例如贪心类问题，或者迪杰斯特拉算法，都可以更加方便的解决问题。

0x01、声明与操作

声明与操作和queue基本一样，例如这段程序：

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int> q;
    q.push(3);
    q.push(4);
    q.push(2);
    cout << q.top();
    return 0;
}

输出的结果是 4 。

如果加上出队程序，出队的序列为4,3,2 。

queue中的pop，size，empty等函数在priority_queue中仍然适用。

0x02、基本数据类型优先级的设置

在前面，priority queue默认的顺序总是数字大的优先级高，而如果我们需要自定义优先级呢

解决这一问题很简单，我们只需要改变一下定义priority queue的方式即可：

priority_queue<ElementType, vector<ElementType>, less<int> > q;

这样，数字大的优先级大

在这里，三个ElementType的类型必须保持一致。这里vector是队列内部用于承载底层数据结构堆的容器，less是对第一个参数的比较类。

less表示数字越大优先级越大（如果是char类型则根据ASCII码来判断），如果希望数字越小优先级越大，只需要将less换成greater即可。例如

priority_queue<ElementType, vector<ElementType>, less<int> > q;

要注意最后一个‘>’与下一个‘>’之间必须有空格。否则编译器会误认为是在做移位运算。

这里很容易记混，再次重复一遍：

less -> 数字大的优先级大，数字大被放在队首。所以先输出数字大的

greater -> 数字小的优先级大，数字小被放在队首。所以先输出数字小的

继续举栗子：

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int, vector<int>, less<int> > q;
    q.push(8);
    q.push(3);
    q.push(5);
    while(!q.empty()){
        cout << q.top() << endl;
        q.pop();
    }
    return 0;
}

运行结果：

栗子：

#include <iostream>
#include <queue>
using namespace std;

int main(){
    priority_queue<int, vector<int>, greater<int> > q;
    q.push(8);
    q.push(3);
    q.push(5);
    while(!q.empty()){
        cout << q.top() << endl;
        q.pop();
    }
    return 0;
}

运行结果：

0x03、结构体的优先级设置

比如博主是个卖水果的，我希望写个程序，帮助我优先卖出贵的水果。

首先我定义一个结构体变量：

struct fruit{
    string name;    //水果名
    int price;      //水果价格
};

如果我们直接把结构体压入priority queue，代码：

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct fruit{
  string name;
  int price;
}f1,f2,f3;

int main(){
    priority_queue<fruit> q;
    /*定义水果和价格*/
    f1.name = "桃子"; f1.price = 3;
    f2.name = "梨"; f2.price = 4;
    f3.name = "苹果"; f3.price = 1;
    /*压入队列*/
    q.push(f1);q.push(f2);q.push(f3);
    while(!q.empty()){
      cout << q.top().name << '\t' << q.top().price << endl;
      q.pop();
    }
    return 0;
}

得到的结果是这样的：

好吧，编译都通不过，大概的意思是，C++中，queue的操作库直接使用了小于号比较大小，而结构体之间不能使用小于号比较，所以，boom。

这里我们可以重载小于号，也就是重新让编译器理解小于号的意思。

（比如编译器默认的小于号意思是直接比较小于号两边数字的大小，我们可以重新定义小于号，让编译器认为小于号是比较结构体中某些变量的大小。如果还是没有太理解，可以想想algorithm头文件中sort函数。这里重新定义小于号，也就相当于定义sort函数中的cmp函数）

（这里必须重载小于号，不能重载大于号，因为从上图中可以看出，C++queue的库函数采用的是小于号，所以定义大于号是没用滴）

我们修改结构体的定义方式，使得重载小于号：

struct fruit{
    string name;
    int price;
    friend bool operator < (fruit f1, fruit f2){//重新定义bool类型操作符‘<’，
                                //‘<’的两边分别是fruit类型的f1和f2
        return f1.price < f2.price;//操作符返回f1.price是否小鱼f2.price
    }
}

这里friend的意思是"友元"。当然，你也可以把return后面的‘<’改为‘>’，这样就可以反着排序了。

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct fruit{
  string name;
  int price;
  friend bool operator < (fruit f1, fruit f2){
      return f1.price < f2.price;
  }
}f1,f2,f3;

int main(){
    priority_queue<fruit> q;
    /*定义水果和价格*/
    f1.name = "桃子"; f1.price = 3;
    f2.name = "梨"; f2.price = 4;
    f3.name = "苹果"; f3.price = 1;
    /*压入队列*/
    q.push(f1);q.push(f2);q.push(f3);
    while(!q.empty()){
      cout << q.top().name << '\t' << q.top().price << endl;
      q.pop();
    }
    return 0;
}

运行结果：

#include <iostream>
#include <queue>
#include <string>
using namespace std;

struct fruit{
  string name;
  int price;
  friend bool operator < (fruit f1, fruit f2){
      return f1.price > f2.price;
  }
}f1,f2,f3;

int main(){
    priority_queue<fruit> q;
    /*定义水果和价格*/
    f1.name = "桃子"; f1.price = 3;
    f2.name = "梨"; f2.price = 4;
    f3.name = "苹果"; f3.price = 1;
    /*压入队列*/
    q.push(f1);q.push(f2);q.push(f3);
    while(!q.empty()){
      cout << q.top().name << '\t' << q.top().price << endl;
      q.pop();
    }
    return 0;
}

运行结果：