cpp priority_queue

概述

• 最大堆
• 时间复杂度：
  • 取堆顶（最大元素）：O(1)
  • 插入/删除堆顶：O(logn)，n为堆中元素数目

自定义判断“大”的函数：

方法一：<操作符成员函数

class T
{
    ...
    bool operator<(const T&r){...}
};
priority_queue<T> q;

方法二：小于函数

auto my_less = [](const T&l, const T&r){...};
// or: auto my_less = [](T l, T r){...};
priority_queue<T, vector<T>, decltype(my_less)> q(my_less);

注意：

• 第二个模板参数是必须的
• 构造函数需要传参自定义的比较函数

成员函数

• 取堆顶 top
• shan’chu堆顶 pop
• 入堆 push, emplace