当前位置:首页 > 开发 > 编程语言 > 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

    震惊

    震惊

编辑推荐
什么是堆: 堆的定义:n个元素的序列k={k0,k1,……,kn-1},当且仅满足条件 (1)ki >= k2i+1 和 ki
1、概述   队列是一种满足先进先出(FIFO)的数据结构,数据从队列头部取出,新的数据从队列尾部
题意:有多少个区间,区间内最大的数减去最小的数差小于k 对每个数它所在的区间,可以只往前找(类似
队列是先进先出的线性表,顾名思义,优先队列则是元素有优先级的队列,出列的顺序由元素的优先级决
优先队列探究 队列的特点是先进先出。通常都把队列比喻成排队买东西,大家都很守秩序,先排队的人就
队列的特点是先进先出。通常都把队列比喻成排队买东西,大家都很守秩序,先排队的人就先买东西。 但
上一节我们写了树以及二叉树的知识 http://blog.csdn.net/wtyvhreal/article/details/43487095 堆是
【0】README 0.1) 本文文字描述部分转自 数据结构与算法分析, 旨在理解 优先队列——二项队列(bi
1.优先队列有两项基本操作:插入(insert)和删除最小项(deleteMin),后者的工作是找出、返回和删
接着上一Pa说。就是如何建立这个堆呢。可以从空的堆开始,然后依次往堆中插入每一个元素,直到所有
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号