一、原型

1.声明

template <
	class T, 
	class Container = vector<T>,
	class Compare = less<typename Container::value_type> > 
class priority_queue;

三个参数:

  • T:参数类型
  • Container:容器类型。默认是用vector容器实现,参数类型必须是T
  • Compare:排序规则。默认是小顶堆弹出std::less<T>

2.本质

其实priority_queue并不是一种基础的容器,而是一种调用别的容器的封装。

// 可以看到它的push操作就是调用别的容器的
void push(const value_type& __x)
{
	c.push_back(__x);
	std::push_heap(c.begin(), c.end(), comp);
}

3.Container

可以是vectorqueuedequeue

4.Compare

优先级队列的内部是大小顶堆实现的,弹出pop()和队首top()都是获得堆首(根结点)的元素。

less<T>变成大顶堆(从上层到下层,堆元素是从大到小,同层之间随便)
greater<T>变成小顶堆(从上层到下层,堆元素是从小到大,同层之间随便)

  1. 顶堆插入一个新元素时,就是插入到最后一个叶子。在这里插入图片描述
  2. 然后这时候整理堆内元素让堆重新满足大小顶堆。关键让新插入的结点和它的父结点进行比较,comp(新插入,它的父结点)
  3. 大顶堆就是让父比子大,即符合less让新插入的比父结点更小;
    小顶堆就是父比子小,即符合greater让新插入的比父结点更大。

详解原理:C++:std::greater()、std::less()、自定义比较函数的规则

二、使用例子

// 头文件
#include <queue>
using namespace std;

1.构造

从上面的构造声明,我们可以看到后两个参数有默认值,可以不写。

/*** 一个参数 ***/
priority_queue<int> p;

/*** 三个参数 ***/
// 注意"> >",因为不写空格可能编译器会解释为右移操作符">>"
priority_queue<int, vector<int>, greater<int> > q;

意思:

  1. 如果是基本类型int之类的,而且确定使用vector,弹出按小顶堆,可以简单写。
  2. 如果想使用升序,则必须写三个参数的形式。
  3. 如果是复杂类型,需要操作符重载以告诉编译器怎么比较的,则必须写三个参数的形式。

2.成员函数

  • 构造好后入队:push(...)
  • 同时构造入队:emplace(...)
  • 出队:pop()
  • 获得队首:top()
  • 大小:size()
  • 是否为空:empty()

再说一遍:优先级队列的内部是大小顶堆实现的,弹出pop()和队首top()都是获得堆首(根结点)的元素。入队push是插入到堆的最后一个叶子节点。

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

int main()
{
    // 初始化优先级队列的对象p
    priority_queue<int> p;

    // 入队操作:push
    // 乱序入队
    p.push(1);
    p.push(3);
    p.push(2);

    // 队的大小
    cout << p.size() << endl;
    // 3

    // 弹出队首
    while (!p.empty())
    {
        cout << p.top() << " ";
        p.pop();
    }
    cout << endl;
    // 3 2 1

    return 0;
}

push(...)emplace(...)的区别就是:对于基本类型来说无所谓,而对于复杂类型,前者是等复杂类型的对象实例化出来后放入它,后者直接在emplace()中传入实例化复杂类型对象的参数,函数自动实例化并放入。

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

// 定义类时同时定义操作符重载
struct Node1
{
    // 要比较的元素
    int x;
    // 构造函数
    Node1(int x,int y) { this->x = x; }
    // 操作符重载函数
    // 必须是具体的操作符<之类的,写()报错
    bool operator<(const Node1 &b) const
    {
        // 实现less中需要的<,大顶堆
        return x < b.x;
    }
};

int main()
{
    // 初始化优先级队列的对象p
    priority_queue<Node1> p;

    // 错误示范
    // p.push(1,0);     报错

    // 入队操作:push
    Node1 node(1,0);
    p.push(node);

    // 入队操作:emplace
    p.emplace(3,0);
    p.emplace(2,0);

    // 队的大小
    cout << p.size() << endl;
    // 3

    // 弹出队首
    while (!p.empty())
    {
        printf("%d ",p.top());
        p.pop();
    }
    cout << endl;
    // 3 2 1

    return 0;
}

3.复杂类型自定义排序

(1)有三种写法,这里用小顶堆举例

  • 定义类时同时定义操作符重载函数:操作符重载函数,必须是具体的操作符<之类的,写()报错
  • 自定义类,自定义比较函数:操作符重载函数,必须是具体的操作符<之类的,写()报错
  • 自定义类,自定义包含比较函数的结构体:操作符重载函数,必须是写()
#include <iostream>
#include <queue>
using namespace std;

/******** 定义类时同时定义操作符重载函数 ********/
struct Node1
{
    // 要比较的元素
    int x;
    // 构造函数
    Node1(int x) { this->x = x; }
    // 操作符重载函数,必须是具体的操作符<之类的,写()报错
    bool operator<(const Node1 &b) const
    {
        // 实现less中需要的<,大顶堆
        return x < b.x;
    }
};

/******** 自定义类,自定义比较函数 ********/
struct Node2
{
    // 要比较的元素
    int x;
    // 构造函数
    Node2(int x) { this->x = x; }
};

// 操作符重载函数,必须是具体的操作符<之类的,写()报错
bool operator<(const Node2 &a, const Node2 &b)
{
    // less,大顶堆
    return a.x < b.x;
}

/******** 自定义类,自定义包含比较函数的结构体 ********/
struct Node3
{
    // 要比较的元素
    int x;
    // 构造函数
    Node3(int x) { this->x = x; }
};

struct cmpClass
{
    // 操作符重载函数,必须是写()
    bool operator()(const Node3 &a, const Node3 &b)
    {
        // less,大顶堆
        return a.x < b.x;
    }
};

int main()
{
    /******** 初始化优先级队列的对象p ********/
    // Node1类型,默认使用vector,小顶堆,同 priority_queue<Node1, vector<Node1>, less<Node1> > p;
    priority_queue<Node1> p;

    // 乱序入队
    p.emplace(1);
    p.emplace(3);
    p.emplace(2);

    // 弹出队首
    while (!p.empty())
    {
        cout << p.top().x << " ";
        p.pop();
    }
    cout << endl;
    // 3 2 1

    /******** 初始化优先级队列的对象q ********/
    // 同 priority_queue<Node2> q;
    priority_queue<Node2, vector<Node2>, less<Node2>> q;

    // 乱序入队
    q.emplace(1);
    q.emplace(3);
    q.emplace(2);

    // 弹出队首
    while (!q.empty())
    {
        cout << q.top().x << " ";
        q.pop();
    }
    cout << endl;
    // 3 2 1

    /******** 初始化优先级队列的对象r ********/
    priority_queue<Node3, vector<Node3>, cmpClass> r;

    // 乱序入队
    r.emplace(1);
    r.emplace(3);
    r.emplace(2);

    // 弹出队首
    while (!r.empty())
    {
        cout << r.top().x << " ";
        r.pop();
    }
    cout << endl;
    // 3 2 1
    return 0;
}

(2)陷阱

我们在(1)的例子中的是这样构造的priority_queue<Node1> p;,对应着第一种写法bool operator<(const Node1 &b) const

因为构造使用默认参数less<T>,而less内部需要我们实现<重载,所以我们才写操作符重载。

这样就给人一种错觉:好像我不需要写操作符重载

PS:再举个小顶堆的例子。

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

// 定义类时同时定义操作符重载
struct Node1
{
    // 要比较的元素
    int x;
    // 构造函数
    Node1(int x) { this->x = x; }
    // 操作符重载函数
    // 必须是具体的操作符>之类的,写()报错
    bool operator>(const Node1 &b) const
    {
        // 实现greater中需要的>,小顶堆
        return x > b.x;
    }
};

int main()
{
    // 初始化优先级队列的对象p,Node1类型
    // 既然要小顶堆,那么就得写全三个参数才有相关的构造器,没有两个的
    priority_queue<Node1, vector<Node1>, greater<Node1>> p;

    // 乱序入队
    p.emplace(1);
    p.emplace(3);
    p.emplace(2);

    // 弹出队首
    while (!p.empty())
    {
        cout << p.top().x << " ";
        p.pop();
    }
    cout << endl;
    // 1 2 3
    return 0;
}

Reference

C++官网 priority_queue
c++优先队列(priority_queue)用法详解
浅谈C++ STL中的优先队列(priority_queue)
C++:std::greater()、std::less()、自定义比较函数的规则

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐