堆

编程语言 / PBDS

本地源文件：docs/lang__pb-ds__pq.md

堆

__gnu_pbds::priority_queue

附：官方文档地址——复杂度及常数测试

---|---

## 模板形参

  * `T`: 储存的元素类型
  * `Compare`: 提供严格的弱序比较类型
  * `Tag`: 是 `__gnu_pbds` 提供的不同的五种堆，Tag 参数默认是 `pairing_heap_tag` 五种分别是：
    * `pairing_heap_tag`：配对堆 官方文档认为在非原生元素（如自定义结构体/`std::string`/`pair`）中，配对堆表现最好
    * `binary_heap_tag`：二叉堆 官方文档认为在原生元素中二叉堆表现最好，不过笔者测试的表现并没有那么好
    * `binomial_heap_tag`：二项堆 二项堆在合并操作的表现要优于二叉堆，但是其取堆顶元素操作的复杂度比二叉堆高
    * `rc_binomial_heap_tag`：冗余计数二项堆
    * `thin_heap_tag`：除了合并的复杂度都和 Fibonacci 堆一样的一个 tag
  * `Allocator`：空间配置器，由于 OI 中很少出现，故这里不做讲解

由于本篇文章只是提供给学习算法竞赛的同学们，故对于后四个 tag 只会简单的介绍复杂度，第一个会介绍成员函数和使用方法．

经作者本机 Core i5 @3.1 GHz On macOS 测试堆的基础操作，结合 GNU 官方的复杂度测试，Dijkstra 测试，都表明： 至少对于 OIer 来讲，除了配对堆的其他四个 tag 都是鸡肋，要么没用，要么常数大到不如 `std` 的，且有可能造成 MLE，故这里只推荐用默认的配对堆．同样，配对堆也优于 `algorithm` 库中的 `make_heap()`．

## 构造方式

要注明命名空间因为和 `std` 的类名称重复．

---|---

成员函数

  • push(): 向堆中压入一个元素，返回该元素位置的迭代器．
  • pop(): 将堆顶元素弹出．
  • top(): 返回堆顶元素．
  • size() 返回元素个数．
  • empty() 返回是否非空．
  • modify(point_iterator, const key): 把迭代器位置的 key 修改为传入的 key，并对底层储存结构进行排序．
  • erase(point_iterator): 把迭代器位置的键值从堆中擦除．
  • join(__gnu_pbds::priority_queue &other): 把 other 合并到 *this 并把 other 清空．

使用的 tag 决定了每个操作的时间复杂度：

| push| pop| modify| erase| Join pairing_heap_tag| 𝑂(1)O(1)| 最坏 Θ(𝑛)Θ(n) 均摊 Θ(log⁡(𝑛))Θ(log⁡(n))| 最坏 Θ(𝑛)Θ(n) 均摊 Θ(log⁡(𝑛))Θ(log⁡(n))| 最坏 Θ(𝑛)Θ(n) 均摊 Θ(log⁡(𝑛))Θ(log⁡(n))| 𝑂(1)O(1) binary_heap_tag| 最坏 Θ(𝑛)Θ(n) 均摊 Θ(log⁡(𝑛))Θ(log⁡(n))| 最坏 Θ(𝑛)Θ(n) 均摊 Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(𝑛)Θ(n)| Θ(𝑛)Θ(n)| Θ(𝑛)Θ(n) binomial_heap_tag| 最坏 Θ(log⁡(𝑛))Θ(log⁡(n)) 均摊 𝑂(1)O(1)| Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(log⁡(𝑛))Θ(log⁡(n)) rc_binomial_heap_tag| 𝑂(1)O(1)| Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(log⁡(𝑛))Θ(log⁡(n)) thin_heap_tag| 𝑂(1)O(1)| 最坏 Θ(𝑛)Θ(n) 均摊 Θ(log⁡(𝑛))Θ(log⁡(n))| 最坏 Θ(log⁡(𝑛))Θ(log⁡(n)) 均摊 𝑂(1)O(1)| 最坏 Θ(𝑛)Θ(n) 均摊 Θ(log⁡(𝑛))Θ(log⁡(n))| Θ(𝑛)Θ(n)

示例

---|---

## __gnu_pbds 迭代器的失效保证（invalidation_guarantee）

在上述示例以及一些实践中（如使用本章的 pb-ds 堆来编写单源最短路等算法），常常需要保存并使用堆的迭代器（如 `__gnu_pbds::priority_queue<int>::point_iterator` 等）．

可是例如对于 `__gnu_pbds::priority_queue` 中不同的 Tag 参数，其底层实现并不相同，迭代器的失效条件也不一样，根据__gnu_pbds 库的设计，以下三种由上至下派生的情况：

  1. 基本失效保证（basic_invalidation_guarantee）：即不修改容器时，点类型迭代器（point_iterator）、指针和引用（key/value）**保持** 有效．

  2. 点失效保证（point_invalidation_guarantee）：即 **修改** 容器后，点类型迭代器（point_iterator）、指针和引用（key/value）只要对应在容器中没被删除 **保持** 有效．

  3. 范围失效保证（range_invalidation_guarantee）：即 **修改** 容器后，除（2）的特性以外，任何范围类型的迭代器（包括 `begin()` 和 `end()` 的返回值）是正确的，具有范围失效保证的 Tag 有 `rb_tree_tag` 和 适用于 `__gnu_pbds::tree` 的 `splay_tree_tag`，以及 适用于 `__gnu_pbds::trie` 的 `pat_trie_tag`．

从运行下述代码中看出，除了 `binary_heap_tag` 为 `basic_invalidation_guarantee` 在修改后迭代器会失效，其余的均为 `point_invalidation_guarantee` 可以实现修改后点类型迭代器 (point_iterator) 不失效的需求．

---|---

本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, H-J-Granger, StudyingFather, Tiphereth-A, countercurrent-time, Enter-tainer, NachtgeistW, Xeonacid, Early0v0, AngelKitty, CCXXXI, cjsoft, diauweb, ezoixx130, GekkaSaori, GoodCoder666, Konano, ksyx, LovelyBuggies, Makkiy, mgt, minghu6, opsiff, ouuan, P-Y-Y, PotassiumWings, SamZhangQingChuan, sshwy, Suyun514, weiyong1024, abc1763613206, alphagocc, Chrogeek, CoderOJ, GavinZhengOI, Gesrua, i-Yirannn, kxccc, lychees, Peanut-Tang, Planet6174, r-value, SukkaW, WAAutoMaton 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用