priority_queue的使用

https://zh.cppreference.com/w/cpp/container/priority_queue

一 定义

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

> class priority_queue;

优先级队列是一种容器适配器，它提供常数时间的（默认）最大元素查找，对数代价的插入与提取。

可以通过用户提供的 Compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。

priority_queue 的作用类似于管理某些随机访问容器中的堆，其优势是不可能意外使堆失效。

底层数据默认std::vector，算法是stl内置的heap算法。

二、模板形参说明

T – 存储元素的类型。T 与 Container::value_type 不是同一类型时非良构。
Container – 用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求，并且它的迭代器必须满足老式随机访问迭代器 (LegacyRandomAccessIterator) 的要求。另外，它必须提供拥有通常语义的下列函数：

back()，例如 std::vector::back()，
push_back()，例如 std::deque::push_back()，
pop_back()，例如 std::vector::pop_back()。
标准容器 std::vector（包括 std::vector<bool>）和 std::deque 满足这些要求。

Compare – 提供严格弱序的比较 (Compare) 类型。
注意比较 (Compare) 形参的定义，使得它的第一实参在弱序中 先于 它的第二实参时返回 true。但因为优先级队列首先输出最大元素，所以“先来”的元素实际上会在最后输出。即队列头含有按照比较 (Compare) 所施加弱序的“最后”元素。

三 例子

#include <functional>
#include <iostream>
#include <queue>
#include <string_view>
#include <vector>

template<typename T>
void pop_println(std::string_view rem, T& pq)
{
    std::cout << rem << ": ";
    for (; !pq.empty(); pq.pop())
        std::cout << pq.top() << ' ';
    std::cout << '\n';
}

template<typename T>
void println(std::string_view rem, const T& v)
{
    std::cout << rem << ": ";
    for (const auto& e : v)
        std::cout << e << ' ';
    std::cout << '\n';
}

int main()
{
    const auto data = {1, 8, 5, 6, 3, 4, 0, 9, 7, 2};
    println("data", data);

    std::priority_queue<int> max_priority_queue;

    // 填充优先级队列。
    for (int n : data)
        max_priority_queue.push(n);

    pop_println("max_priority_queue", max_priority_queue);

    // std::greater<int> 使得最大优先队列表现为最小优先队列。
    std::priority_queue<int, std::vector<int>, std::greater<int>>
        min_priority_queue1(data.begin(), data.end());

    pop_println("min_priority_queue1", min_priority_queue1);

    // 定义最小优先队列的另一种方法
    std::priority_queue min_priority_queue2(data.begin(), data.end(), std::greater<int>());

    pop_println("min_priority_queue2", min_priority_queue2);

    // 使用自定义的函数对象来比较元素。
    struct
    {
        bool operator()(const int l, const int r) const { return l > r; }
    } customLess;

    std::priority_queue custom_priority_queue(data.begin(), data.end(), customLess);

    pop_println("custom_priority_queue", custom_priority_queue);

    // 使用 lambda 来比较元素。
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1); };
    std::priority_queue<int, std::vector<int>, decltype(cmp)> lambda_priority_queue(cmp);

    for (int n : data)
        lambda_priority_queue.push(n);

    pop_println("lambda_priority_queue", lambda_priority_queue);
}

输出：

data: 1 8 5 6 3 4 0 9 7 2
max_priority_queue: 9 8 7 6 5 4 3 2 1 0
min_priority_queue1: 0 1 2 3 4 5 6 7 8 9
min_priority_queue2: 0 1 2 3 4 5 6 7 8 9
custom_priority_queue: 0 1 2 3 4 5 6 7 8 9
lambda_priority_queue: 8 9 6 7 4 5 2 3 0 1

4 注意

1.priority_queue默认是std::less，是大顶堆
2.当指明std::greater（小顶堆时），也通常需要将第二个模板参数写出，默认是std::vector<>
3.为什么std::less是大顶堆，而std::greater是小顶堆呢
根因在于其底层实现。
less：左数小于右数时，返回true，否则返回false。
在堆的调整过程中，对于大顶堆，如果当前插入的节点值大于其父节点，那么就应该向上调整。其父节点索引小于当前插入节点的索引，也就是父节点是左数，插入节点是右值，可以看到，左数小于右数时，要向上调整，也就是Compare函数应该返回true，正好是less。