优先级队列用法详解（priority

优先级队列用法详解（priority_queue）

阅读量：5794 次

发布时间：2019-06-18

本文共 3543 字，大约阅读时间需要 11 分钟。

由于优先级队列的内部数据结构为堆，所以这里先介绍堆的一些操作。

堆的一些函数操作在algorithm头文件中

//在[first, last)范围内构造最大堆,first,last 可以是vector指针也可以是数组指针make_heap(first ,last)make_heap(first ,last, cmpObject)

默认情况下是建立最大堆，即首元素为两个地址间的最大值。默认为less<int>，可以改为greater<int>即为建立最小堆

pop_heap(first ,last)pop_heap(first ,last, cmpObject)

将front（即第一个最大元素）移动到end的前部，同时将剩下的元素重新构造成(堆排序)一个新的heap。

push_heap(first ,last)push_heap(first ,last, cmpObject)

对刚插入的（尾部）元素做堆排序。在进行push_heap操作之前，除了最后一个元素以外的其他元素必须构成一个最大堆，

否则会报错。

sort_heap(first ,last)sort_heap(first ,last, cmpObject)

将一个堆做排序,最终成为一个有序的系列，可以看到sort_heap时，必须先是一个堆（两个特性：1、最大元素在第一个 2、添加或者删除元素以对数时间），因此必须先做一次make_heap.

先写一个用 STL 里面堆算法实现的与真正的STL里面的priority_queue 用法相

似的 priority_queue，以加深对priority_queue 的理解

#include 
     
      #include 
      
       #include 
       
         using namespace std; class priority_queue{    private:        vector
        
          data;    public:        void push( int t ){            data.push_back(t);            push_heap( data.begin(), data.end());        }        void pop(){            pop_heap( data.begin(), data.end() );            data.pop_back();        }        int top()    { return data.front(); }        int size()   { return data.size();  }        bool empty() { return data.empty(); }}; int main(){    priority_queue  test;    test.push( 3 );    test.push( 5 );    test.push( 2 );    test.push( 4 );    test.push(10);    test.push(1);    while( !test.empty() ){        cout << test.top() << endl;            test.pop(); }    return 0;}

模板声明带有三个参数，priority_queue<Type, Container, Functional>

　　Type 为数据类型， Container 为保存数据的容器， Functional 为元素比较方式。

　　Container 必须是用数组实现的容器，比如 vector, deque 但不能用list.

　　STL里面默认用的是vector. 比较方式默认用operator< , 所以如果你把后面俩个

　　参数缺省的话，优先队列就是大顶堆，队头元素最大。

下面的程序为建立一个最小堆的例子 priority_queue<int,vector<int>,greater<int>> q;

#include 
      
       #include 
       
         using namespace std; int main(){    priority_queue

, greater

> q; for( int i= 0; i< 10; ++i ) q.push( rand() ); while( !q.empty() ){ cout << q.top() << endl; q.pop(); } getchar(); return 0;}

View Code

自定义类型Node的优先级队列，重载比较运算符'<'：

#include 
      
       #include 
       
         using namespace std; struct Node{    int x, y;    Node( int a= 0, int b= 0 ):        x(a), y(b) {}}; bool operator<( Node a, Node b ){    if( a.x== b.x ) return a.y> b.y;    return a.x> b.x;} int main(){    priority_queue
        
          q;    for( int i= 0; i< 10; ++i )    q.push( Node( rand(), rand() ) );    while( !q.empty() ){        cout << q.top().x << ' ' << q.top().y << endl;        q.pop();    }    getchar();    return 0;}

View Code

重载‘<’之后可以只带一个模板参数定义优先级队列对象，但不能声明priority_queue<Node, vector<Node>, greater<Node> >

这种类型，原因是greater<Node>没有定义，要想定义上述形式必须定义一个比较的类cmp，具体实现如下代码。

#include 
      
       #include 
       
         using namespace std; struct Node{    int x, y;    Node( int a= 0, int b= 0 ):        x(a), y(b) {}}; struct cmp{    bool operator() ( Node a, Node b ){        if( a.x== b.x ) return a.y> b.y;        return a.x> b.x; }}; int main(){    priority_queue
        
         , cmp> q;    for( int i= 0; i< 10; ++i )    q.push( Node( rand(), rand() ) );    while( !q.empty() ){        cout << q.top().x << ' ' << q.top().y << endl;        q.pop();    }    getchar();    return 0;}

View Code

参考博文：

　　http://blog.163.com/zjut_nizhenyang/blog/static/1695700292010101632059540/

　　http://blog.csdn.net/fuyufjh/article/details/47144869

　　http://blog.sina.com.cn/s/blog_959bf1d3010191h1.html

转载于:https://www.cnblogs.com/NeilZhang/p/6485013.html

你可能感兴趣的文章