C++STL

STL | priority_queue（优先队列）基本用法

2019-07-11  本文已影响3人  0与1的邂逅

写在前面：

priority_queue ，又称优先队列 ，是一个容器——允许在O(lg N)时间复杂度下插入 数据、在O(1)时间复杂度下取得容器内最大（最小）值 。

其本质就是一个堆 ，只是比我们自己手写堆 多了一些优化罢了（没有优化也就不会纳入STL中啦）。

使用STL的priority_queue需要包含头文件queue ，即

#include<queue>

优先队列：

一. 定义

优先队列priority_queue的定义如下：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
Parameter Description Default
T The type of object stored in the priority queue.
Container The type of the underlying container used to implement the priority queue. vector<T>
Compare The comparison function used to determine whether one element is smaller than another element.If Compare(x,y) is true, then x is smaller than y.The element returned by Q.top() is the largest element in the priority queue.That is, it has the property that, for every other element x in the priority queue, Compare(Q.top(), x) is false. less<T>
参数 描述 默认值
数据类型 T 优先队列中存放的数据类型
容器 用于实现优先队列（潜在）的容器类型 vector<T>
比较函数（优先级） 用于确定一个元素是否小于另一个元素的比较函数。如果Compare(x, y)是正确的,那么x小于y，优先队列Q.top()返回的就是最大的元素。此时，优先队列队头元素Q.top()与优先队列Q中所有其他元素x进行比较，即Compare(Q.top (), x) 是错误的 less<T>

  • Container：必须是用数组实现的容器，比如 vector, deque，但不能用 list。STL里面默认用的是 vector。

  • Compare：比较方式默认用使用less<T>，operator <（小于号）。

  • 所以如果你把后面俩个参数缺省的话，优先队列就是大顶堆，队头元素最大。

二. 默认的优先队列——大顶堆

priority_queue<int>que;
等价于
priority_queue<int,vector<int>,less<int> >que;
注意需要添加头文件vector，即#include<vector> 
可以在下面的测试程序中，动手尝试一下

#include<cstdio>
#include<iostream>
#include<queue>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;

priority_queue<int>que;// 默认的优先队列 
//priority_queue<int,vector<int>,less<int> >que;
int test[1010];

int main()
{
    // 使用一个简易的随机数（不能超过值RAND_MAX）进行测试 
    srand((int)time(0)); 
    for(int i=0;i<100;i++)test[i]=rand(),que.push(test[i]);
    // 入队列之前 
    cout<<"Before:\n";
    for(int i=0;i<100;i++)cout<<test[i]<<" ";
    cout<<endl;
    // 入队列之后 
    cout<<"After:\n";
    while(!que.empty())
    {
        cout<<que.top()<<" ";
        que.pop();
    }
}
默认的优先队列

三. 更改比较函数——仿函数greater<T>

默认的优先队列是大顶堆，那么，如果我们想要变为小顶堆 ，可以使用STL中的仿函数
greater<T>（默认的使用的是less<T>）。

对上面的程序中，优先队列的定义进行如下修改，

priority_queue<int,vector<int>,greater<int> >que;

重新运行程序，得到下面结果（可以看出此时优先队列相当于一个小顶堆 ）。

greater<T>

四. 自定义类型——大顶堆

STL中的仿函数less<T>和greater<T>的使用范围仅限于基本类型，当优先队列需要保存我们自定义的数据类型时，我们需要重载小于号（operator <）或者写仿函数，这两种方式定义的优先队列稍有不同。

① 重载小于运算符 <：

// 重载 < 运算符，实现大顶堆
//（堆顶元素：先根据x，选择x最大的元素；若两个元素的x值相同，再根据y，选择两者中y较大的元素） 
bool operator<(My_Type a,My_Type b)
{
    // 定义排序规则 
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x; 
}
// 定义优先队列
priority_queue<My_Type>que;

② 仿函数：

// 仿函数，实现大顶堆 
struct cmp
{
    // 定义排序规则 
    bool operator() (My_Type a,My_Type b )
    { 
        if(a.x==b.x)return a.y<b.y;
        return a.x<b.x; 
    }
}; 
// 定义优先队列
priority_queue<My_Type,vector<My_Type>,cmp>que;

③ 完整代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
// 自定义一种结构体类型 
typedef struct
{
    int x;
    int y;
}My_Type;
// 仿函数，实现大顶堆 
struct cmp
{
    // 定义排序规则 
    bool operator() (My_Type a,My_Type b )
    { 
        if(a.x==b.x)return a.y<b.y;
        return a.x<b.x; 
    }
}; 
// 重载 < 运算符，实现大顶堆
//（堆顶元素：先根据x，选择x最大的元素；若两个元素的x值相同，再根据y，选择两者中y较大的元素） 
bool operator<(My_Type a,My_Type b)
{
    // 定义排序规则 
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x; 
}
vector<My_Type>vec;
//priority_queue<My_Type,vector<My_Type>,cmp>que;
priority_queue<My_Type>que; 

int main()
{
    My_Type temp;
    srand((int)time(NULL)); 
    for(int i=0;i<10;i++)
    {
        temp.x=rand();
        temp.y=rand();
        vec.push_back(temp);
        que.push(temp);
    }
    cout<<"Before:\n";
    for(int i=0;i<10;i++)
    {
        cout<<vec[i].x<<" "<<vec[i].y<<endl;
    }
    cout<<"\nAfter:\n";
    while(!que.empty())
    {
        temp=que.top();
        cout<<temp.x<<" "<<temp.y<<endl;
        que.pop();
    }   
}
自定义类型——大顶堆

五. 自定义类型——小顶堆

若要实现一个小顶堆，与上面的程序差不多，仅仅需要更改一下排序规则即可：
① 重载小于运算符 <：

// 重载 < 运算符，实现小顶堆 
bool operator<(My_Type a,My_Type b)
{
    // 定义排序规则 
    if(a.x==b.x) return a.y>b.y;
    return a.x>b.x; 
}

② 仿函数：

// 仿函数，实现小顶堆 
struct cmp
{
    // 定义排序规则 
    bool operator() (My_Type a,My_Type b )
    { 
        if(a.x==b.x)return a.y>b.y;
        return a.x>b.x; 
    }
};

六. 优先队列的用途：

一开始我们便提到了，优先对了是一个容器——允许在O(lg N)时间复杂度下插入 数据、在O(1)时间复杂度下取得容器内最大（最小）值 。

正是由于优先队列这样的特征（时间复杂度低），使得在一些算法中可以使用优先队列来进行优化：

(PS：未完待续，遇到了再做补充)

七. 其他一些常见的函数：

函数 功能
empty() 如果优先队列为空，则返回真
top() 返回优先队列中有最高优先级的元素
pop() 删除第一个元素
push() 插入一个元素
size() 返回优先队列中拥有的元素的个数

写在最后：

参考资料：

优先队列，虽然叫队列，但是其本质却是堆（一种特殊的二叉树）。

看待一个人，以貌取人往往是不够的，更多的是看他生活的点滴，从生活的蛛丝马迹中了解一个人。

上一篇 下一篇

猜你喜欢

热点阅读