当前位置:首页 > 开发 > 编程语言 > C/C++ > 正文

c++-STL-priority_queue(优先队列)

发表于: 2013-09-04   作者:追梦--   来源:转载   浏览:
摘要:     如果我们在竞赛中如果用堆来实现一个优先队列,代码量不说,还有可能出现低级错误。这时候,c++ STL就是我们比赛中的一个好助手了。     和其他STL容器一样,priority_queue一样的又插入和删除元素。顾名思义,priority_queue就是权值大的优先出列,我们只需要插入数据,并拟定规则(重载操作符),prior
    如果我们在竞赛中如果用堆来实现一个优先队列,代码量不说,还有可能出现低级错误。这时候,c++ STL就是我们比赛中的一个好助手了。
    和其他STL容器一样,priority_queue一样的又插入和删除元素。顾名思义,priority_queue就是权值大的优先出列,我们只需要插入数据,并拟定规则(重载操作符),priority_queue 自动排序(还是利用大顶堆,原理在此不详述)。
priority_queue 的构造函数有七种,这里只讲述比较重要的
      priority_queue<int> que;
      priority_queue<int,list<int>> (复制构造函数)
      priority_queue<int,vector<int>,cmp>(cmp为比较函数)
常用的方法有:
c.top()          返回队列头部数据
c.push(elem) 在队列尾部增加elem数据
c.pop()          队列头部数据出队
c.empty() 判断队列是否为空
c.size() 返回队列中数据的个数
     

    但我们要将自己定义的类型使用priority_queue怎么办,重载运算符,代码如下:

#include<iostream>
#include<queue>
using namespace std;
struct node{
      int x;
      int y;
      friend bool operator < (const node a,const node b){
           if(a.x!=b.x){
              return b.x<a.x;             
           }else{
              return b.y<a.y;      
           }       
           //x小的先出列,相同再根据 y 的大小 
      }       
};
int main(){
     priority_queue<node> que;
     node nodeList[6];
     for(int i=1;i<6;i++){
         node newNode;
         newNode.x = i;
         newNode.y = i;   
         que.push(newNode);    
     }
     node newNode; 
     newNode.x = 3; newNode.y=4;
     que.push(newNode);
     while(!que.empty()){
         node node1 = que.top();
         que.pop();
         cout << node1.x << " " << node1.y << endl;                    
     }
     system("pause");
     return 0;
} 

c++-STL-priority_queue(优先队列)

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号