优先队列学习

一、相关定义

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

二、priority_queue

基本操作:

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

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

push()        加入一个元素

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

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

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

头文件:

#include <queue>   下面看最基本的用法:从大到小输出
#include <iostream>
#include<queue>
#include<algorithm>
using namespace std;

int main(){
    priority_queue<int>que;//采用默认优先级构造队列

    for(int i=0;i<10;i++)
    {
        int x=rand()%10;
        que.push(x);
    }
    cout<<"采用默认优先关系:"<<endl;
    while(!que.empty())//从大到小的顺序 
    {
        cout<<que.top()<<" ";
        que.pop();
    }
    cout<<endl;
    return 0;
}

 

 

下面是按照从小到大输出  greater的用法

#include <iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

int main()
{
    priority_queue<int,vector<int>,greater<int> >que;//采用默认优先级构造队列

    for(int i=0;i<10;i++)
    {
        int x=rand()%10;
        que.push(x);
    }
    cout<<"采用greater的优先关系:"<<endl;
    while(!que.empty())//从小到大输出 
    {
        cout<<que.top()<<" ";
        que.pop();
    }
    cout<<endl;
    return 0;
}

 

下面看结构体的使用

#include <iostream>
#include<queue>
#include<algorithm>
#include<vector>
using namespace std;

struct number1
{
    int x;//下面两种都可以 
    /*
    bool operator < (const number1 &a) const
    {
        return x>a.x;
    }*/
    friend bool operator < (number1 a,number1 b)
    {
        return a.x>b.x;//x小的优先级大 
    }
};

int main()
{
    priority_queue<number1>que;//

    for(int i=0;i<10;i++)
    {
        int x=rand()%10;
        number1 n;
        n.x=x;
        que.push(n);
    }
    cout<<"采用结构体定义的优先关系:"<<endl;
    while(!que.empty())//从小到大 
    {
        cout<<que.top().x<<" ";
        que.pop();
    }
    cout<<endl;
    return 0;
}

 

 

上一篇:【算法总结】哈夫曼树


下一篇:Mybatis学习第20节 -- 嵌套结果