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

发布于 / 数据结构与算法 / Comments Off on 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;
}

运行结果:

转载原创文章请注明,转载自: 斐斐のBlog » C语言-优先队列(priority queue)详解
评论已关闭