c++ 优先级队列_低优先级队列要等几局

c++ 优先级队列_低优先级队列要等几局作者有话说:本来兴致勃勃的准备写一篇优先级队列的总结,但查资料时发现一篇写的不错的博文,偷个懒!!!!!!!!!!!转载大神的就ok了。https://www.cnblogs.com/xzxl/p/7266404.html一、相关定义优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性,就是队列中最大的元素总是位于队首,所以出队时,并非按照先进先出的原则进行,而…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

作者有话说:本来兴致勃勃的准备写一篇优先级队列的总结,但查资料时发现一篇写的不错的博文,偷个懒!!!!!!!!!!!

转载大神的就ok了。https://www.cnblogs.com/xzxl/p/7266404.html

一、相关定义

优先队列容器与队列一样,只能从队尾插入元素,从队首删除元素。但是它有一个特性,就是队列中最大的元素总是位于队首,所以出队时,并非按照先进先出的原则进行,而是将当前队列中最大的元素出队。这点类似于给队列里的元素进行了由大到小的顺序排序。元素的比较规则默认按元素值由大到小排序,可以重载“<”操作符来重新定义比较规则。

优先级队列可以用向量(vector)或双向队列(deque)来实现(注意list container不能用来实现queue,因为list的迭代器不是任意存取iterator,而pop中用到堆排序时是要求randomaccess iterator 的!):
priority_queue<vector<int>, less<int> > pq1;     // 使用递增less<int>函数对象排序
priority_queue<deque<int>, greater<int> > pq2;   // 使用递减greater<int>函数对象排序
其成员函数有“判空(empty)” 、“尺寸(Size)” 、“栈顶元素(top)” 、“压栈(push)” 、“弹栈(pop)”等。

 

二、priority_queue

基本操作:

empty()      如果队列为空,则返回真

pop()    删除对顶元素,删除第一个元素

push()        加入一个元素

size()      返回优先队列中拥有的元素个数

top()     返回优先队列对顶元素,返回优先队列中有最高优先级的元素

在默认的优先队列中,优先级高的先出队。在默认的int型中先出队的为较大的数。

头文件:

#include <queue>

声明方式:

1、普通方法:

priority_queue<int> q;                 //通过操作,按照元素从大到小的顺序出队

priority_queue<int,vector<int>, greater<int> > q;    //通过操作,按照元素从小到大的顺序出队

2、自定义优先级:

struct cmp {     

  operator bool ()(int x, int y)     

  {        

     return x > y;   // x小的优先级高       //也可以写成其他方式,如: return p[x] > p[y];表示p[i]小的优先级高

  }

};

priority_queue<int, vector<int>, cmp> q;    //定义方法

//其中,第二个参数为容器类型。第三个参数为比较函数。

3、结构体声明方式:

struct node {     

  int x, y;     

  friend bool operator < (node a, node b)     

  {         

    return a.x > b.x;    //结构体中,x小的优先级高     

  }

};

priority_queue<node>q;   //定义方法

//在该结构中,y为值, x为优先级。

//通过自定义operator<操作符来比较元素中的优先级。

//在重载”<”时,最好不要重载”>”,可能会发生编译错误

 

三、代码实现

优先队列,其构造及具体实现我们可以先不用深究,我们现在只需要了解其特性,及在做题中的用法。
以一个例子来解释吧(呃,写完才发现,这个代码包函了几乎所有我们要用到的用法,仔细看看吧):
/*优先队列的基本使用    2017/8/1    xzxl*/ 
#include<stdio.h> 
#include<functional> 
#include<queue> 
#include<vector> 
using namespace std; 
//定义结构,使用运算符重载,自定义优先级1 
struct cmp1{ 
    bool operator ()(int &a,int &b){ 
        return a>b;//最小值优先 
    } 
}; 
struct cmp2{ 
    bool operator ()(int &a,int &b){ 
        return a<b;//最大值优先 
    } 
}; 
//定义结构,使用运算符重载,自定义优先级2 
struct number1{ 
    int x; 
    bool operator < (const number1 &a) const { 
        return x>a.x;//最小值优先 
    } 
}; 
struct number2{ 
    int x; 
    bool operator < (const number2 &a) const { 
        return x<a.x;//最大值优先 
    } 
}; 
int a[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0}; 
   
int main() 
{   priority_queue<int>que;//采用默认优先级构造队列 
   
    priority_queue<int,vector<int>,cmp1>que1;//最小值优先 
    priority_queue<int,vector<int>,cmp2>que2;//最大值优先 
   
    priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误, 
                                                      //这是右移运算符,所以这里用空格号隔开 
    priority_queue<int,vector<int>,less<int> >que4;最大值优先 
   
    priority_queue<number1>que5; 
    priority_queue<number2>que6; 
   
    int i; 
    for(i=0;a[i];i++){ 
        que.push(a[i]); 
        que1.push(a[i]); 
        que2.push(a[i]); 
        que3.push(a[i]); 
        que4.push(a[i]); 
    } 
    for(i=0;num1[i].x;i++) 
        que5.push(num1[i]); 
    for(i=0;num2[i].x;i++) 
        que6.push(num2[i]); 
   
   
    printf("采用默认优先关系:\n(priority_queue<int>que;)\n"); 
    printf("Queue 0:\n"); 
    while(!que.empty()){ 
        printf("%3d",que.top()); 
        que.pop(); 
    } 
    puts(""); 
    puts(""); 
   
    printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n"); 
    printf("Queue 1:\n"); 
    while(!que1.empty()){ 
        printf("%3d",que1.top()); 
        que1.pop(); 
    } 
    puts(""); 
    printf("Queue 2:\n"); 
    while(!que2.empty()){ 
        printf("%3d",que2.top()); 
        que2.pop(); 
    } 
    puts(""); 
    puts(""); 
    printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n"); 
    printf("Queue 3:\n"); 
    while(!que3.empty()){ 
        printf("%3d",que3.top()); 
        que3.pop(); 
    } 
    puts(""); 
    printf("Queue 4:\n"); 
    while(!que4.empty()){ 
        printf("%3d",que4.top()); 
        que4.pop(); 
    } 
    puts(""); 
    puts(""); 
    printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n"); 
    printf("Queue 5:\n"); 
    while(!que5.empty()){ 
        printf("%3d",que5.top()); 
        que5.pop(); 
    } 
    puts(""); 
    printf("Queue 6:\n"); 
    while(!que6.empty()){ 
        printf("%3d",que6.top()); 
        que6.pop(); 
    } 
    puts(""); 
    return 0; 
} 
/*
运行结果 :
采用默认优先关系:
(priority_queue<int>que;)
Queue 0:
83 72 56 47 36 22 14 10  7  3
  
采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
Queue 1:
 7 10 14 22 36 47 56 72 83 91
Queue 2:
83 72 56 47 36 22 14 10  7  3
  
采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
Queue 3:
 7 10 14 22 36 47 56 72 83 91
Queue 4:
83 72 56 47 36 22 14 10  7  3
  
采用结构体自定义优先级方式二:
(priority_queue<number>que)
Queue 5:
 7 10 14 22 36 47 56 72 83 91
Queue 6:
83 72 56 47 36 22 14 10  7  3
*/ 

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/190131.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号