企业官网建设流程全解析

OI-wiki 配对堆（Pairing Heap）详解：自调整可并堆的结构、实现与复杂度分析

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读：配对堆（Pairing Heap）是 OI / ICPC 竞赛中常用的一种可并堆（Meldable Heap），以结构简单、合并极快而著称，支持插入、查询/删除最小值、合并以及修改元素等全部堆操作。本文以 OI-wiki 的配对堆文档 为主体，结合仓库内源码与配套文档，系统讲解其儿子-兄弟表示法、各操作的 C++ 实现、两步合并的删除流程与均摊复杂度结论，并介绍它在__gnu_pbds标准库中的工程形态，帮助你写出可直接用于竞赛的配对堆代码。

引入：为什么需要配对堆

配对堆是一种可并堆，即除了支持普通堆的插入、查询/删除最值之外，还支持快速合并两个堆的数据结构。它的核心优势是速度快且结构简单：无需维护树大小、深度、排名等额外信息，任何一棵满足堆性质的多叉树都是一个合法的配对堆。正因如此，配对堆在实践中拥有优秀的常数，在竞赛中常用于需要动态合并集合最小值的问题，例如 Dijkstra 优化、K 短路等场景。

需要注意的一点是：配对堆的复杂度是基于势能分析的均摊复杂度，因此它无法可持久化，这一点与左偏树（见 左偏树文档）等结构有所区别。

定义：满足堆性质的多叉树

配对堆是一棵满足堆性质的带权多叉树：以最小堆为例，每个节点的权值都小于或等于它的所有儿子（如下图）。

与常见的二叉堆（二叉堆文档）不同，配对堆不要求树是完全二叉树，也不维护节点深度、子树大小或排名等信息——任何一个满足堆性质的树都是合法的配对堆。这种"零额外信息"的设计，正是配对堆拥有出色常数的基础：作为对比，斐波那契堆虽然理论复杂度更优，但因为需要维护大量额外信息（度数、标记、根链表等），实际常数相当糟糕。

儿子-兄弟表示法

配对堆在存储上通常使用儿子-兄弟表示法（left-child right-sibling）：一个节点的所有儿子形成一个单向链表，每个节点只保存"第一个儿子"（即链表的头节点）的指针，以及"下一个兄弟"的指针（如下图）。

这种方式不仅便于实现合并操作，也为后续的复杂度分析提供了便利。对应的结构体定义如下：

struct Node { T v; // T 为权值类型 Node *child, *sibling; // child 指向该节点第一个儿子，sibling 指向该节点的下一个兄弟 // 若该节点没有儿子/下个兄弟则指针指向 nullptr };

过程：五大核心操作

配对堆的全部操作都建立在一个最基础的meld（合并）操作之上。下面依次介绍各操作的原理与实现。

查询最小值

由堆性质可知，配对堆根节点的权值一定是最小值，因此查询最小值只需直接返回根节点即可，复杂度为 $O(1)$。

合并（meld）

合并两个配对堆的操作非常简单：令两个根中权值较小的一个成为新堆的根，然后把另一个根作为它的儿子插入（见下图）。

Node* meld(Node* x, Node* y) { // 若有一个为空则直接返回另一个 if (x == nullptr) return y; if (y == nullptr) return x; if (x->v > y->v) std::swap(x, y); // swap 后 x 为权值小的堆，y 为权值大的堆 // 将 y 设为 x 的儿子 y->sibling = x->child; x->child = y; return x; // 新的根节点为 x }

实现中需要留意儿子链表的排序约定：儿子的链表按插入时间排序，最右边的节点最早成为父节点的儿子，最左边的节点最近成为父节点的儿子。这一约定在删除最小值操作的第二阶段合并方向判断中至关重要。

插入（push）

插入操作没有任何额外复杂度：把新元素看作一个只含单节点的配对堆，直接与原堆meld即可。

删除最小值（delete-min）

上面的所有操作都"十分偷懒"，完全没有对数据结构进行额外维护，因此删除最小值必须精心设计，否则会破坏整体复杂度。

删除最小值时，根节点即最小值。拿掉根节点后，它的所有儿子构成了一片森林；而配对堆必须保持为一棵树，所以需要按某种顺序把这些儿子全部合并起来。

一个最朴素的想法是：用meld把儿子们从左到右挨个并起来。这样做正确性显然，但单次操作复杂度会退化到 $O(n)$。为了保住均摊复杂度，必须采用**"两步走"合并方法**：

1. 第一步（配对）：把儿子们两两配成一对，用meld把配成同一对的两个儿子合并到一起；
2. 第二步（从右往左合并）：将新产生的堆从右往左（即从老的儿子到新的儿子的方向）挨个合并在一起。

先实现辅助函数merges，其作用是合并一个节点的所有兄弟：

Node* merges(Node* x) { if (x == nullptr || x->sibling == nullptr) return x; // 如果该树为空或他没有下一个兄弟，就不需要合并了，return Node* y = x->sibling; // y 为 x 的下一个兄弟 Node* c = y->sibling; // c 是再下一个兄弟 x->sibling = y->sibling = nullptr; // 拆散 return meld(merges(c), meld(x, y)); // 核心部分 }

最后一行是该函数的核心，它由三部分组成：

1. meld(x, y)"配对"了 x 和 y；
2. merges(c)递归合并 c 和它的兄弟们；
3. 将上面两个操作产生的两个新树合并。

这里特别提醒：第二步的合并方向必须是从右往左，该递归实现已经天然保证了这一顺序。如果读者要自行编写迭代版本，请务必注意保持从右往左的顺序，否则复杂度将失去保证。

有了merges，delete-min的实现就顺理成章了：

Node* delete_min(Node* x) { Node* t = merges(x->child); delete x; // 如果需要内存回收 return t; }

减小一个元素的值（decrease-key）

decrease-key是配对堆在 Dijkstra 等算法中的关键操作。要实现它，需要给节点额外添加一个父指针（father），其语义是：当节点有左兄弟时，father指向其左兄弟而非实际的父节点；否则指向其实际的父节点；若该节点是根节点则指向nullptr。

首先修改节点的定义：

struct Node { LL v; int id; Node *child, *sibling; Node *father; // 新增：父指针，若该节点为根节点则指向空节点 nullptr };

meld需要同步维护父指针：

Node* meld(Node* x, Node* y) { if (x == nullptr) return y; if (y == nullptr) return x; if (x->v > y->v) std::swap(x, y); if (x->child != nullptr) { // 新增：维护父指针 x->child->father = y; } y->sibling = x->child; y->father = x; // 新增：维护父指针 x->child = y; return x; }

merges同样需要维护父指针：

Node *merges(Node *x) { if (x == nullptr) return nullptr; x->father = nullptr; // 新增：维护父指针 if (x->sibling == nullptr) return x; Node *y = x->sibling, *c = y->sibling; y->father = nullptr; // 新增：维护父指针 x->sibling = y->sibling = nullptr; return meld(merges(c), meld(x, y)); }

接下来考虑decrease-key的实现思路。当我们减少节点x的权值后，以x为根的子树内部仍然满足配对堆性质，但x和它的父亲之间可能不再满足堆性质。因此做法是：把整棵以x为根的子树从原树中剖出来，此时两棵树都各自符合配对堆性质，再把它们meld合并回去，即完成全部操作。

// root 为堆的根，x 为要操作的节点，v 为新的权值，调用时需保证 v <= x->v // 返回值为新的根节点 Node *decrease_key(Node *root, Node *x, LL v) { x->v = v; // 更新权值 if (x == root) return x; // 如果 x 为根，则直接返回 // 把 x 从 fa 的子节点中剖出去，这里要分 x 的位置讨论 if (x->father->child == x) { x->father->child = x->sibling; } else { x->father->sibling = x->sibling; } if (x->sibling != nullptr) { x->sibling->father = x->father; } x->sibling = nullptr; x->father = nullptr; return meld(root, x); // 重新合并 x 和根节点 }

注意剖出节点时需要区分x是父亲的第一个儿子（用father->child == x判断）还是后面的兄弟（此时通过father->sibling连接），并正确维护被剖位置前后节点的指针关系，避免破坏儿子链表。

复杂度分析

配对堆结构与实现虽然简单，时间复杂度分析却并不容易。

• 原论文（Fredman, Sedgewick, Sleator & Tarjan 的The pairing heap: a new form of self-adjusting heap）仅证明了meld和delete-min操作的均摊复杂度均为 $O(\log n)$，并提出了一个猜想：配对堆的各个操作可能都具有与斐波那契堆相同的复杂度。
• 遗憾的是，后续研究（On the efficiency of pairing heaps and related data structures）发现：不维护额外信息的配对堆，在特定操作序列下，decrease-key操作的均摊复杂度下界至少为 $\Omega(\log\log n)$。
• 目前对复杂度上界较好的估计包括：Iacono 给出的 $O(1)$meld、$O(\log n)$decrease-key（Improved upper bounds for pairing heaps）；以及 Pettie 给出的 $O(2^{2\sqrt{\log\log n}})$meld和decrease-key（Towards a Final Analysis of Pairing Heaps）。

需要特别强调的是：上述复杂度均为均摊复杂度，不同结果不能分别取最小值来组合使用（例如不能同时采用某论文的 $O(1)$meld与另一论文的 $O(\log n)$decrease-key作为最终结论）。更详细的证明过程与参考文献，请参阅 OI-wiki 配对堆文档。

工程实践：__gnu_pbds中的配对堆

配对堆的工程价值在 C++ 标准库扩展__gnu_pbds中得到了充分体现。在 pb-ds 优先队列文档 中可以看到，__gnu_pbds::priority_queue的Tag模板参数默认就是pairing_heap_tag（配对堆），其五种可选的Tag分别是：

__gnu_pbds::priority_queue提供的成员函数与配对堆的上述操作一一对应：push返回point_iterator，支持modify(point_iterator, key)（对应 decrease-key）、erase(point_iterator)、join(other)（对应 meld）等。其模板用法为：

#include <ext/pb_ds/priority_queue.hpp> using namespace __gnu_pbds; __gnu_pbds::priority_queue<int>::point_iterator id; // 点类型迭代器 id = q.push(1);

在 pb-ds 文档的示例代码 中可以看到完整的push/pop/top/modify/erase/join演示，并且pairing_heap_tag具备point_invalidation_guarantee（点失效保证），即修改容器后，只要迭代器对应的元素未被删除，点类型迭代器、指针和引用都保持有效——这对需要在 Dijkstra 等算法中长期保存节点迭代器的场景非常关键。

小结

• 结构：配对堆是不维护任何额外信息的多叉堆，采用儿子-兄弟表示法存储，实现极为简洁；
• 操作：meld是基石，delete-min通过"两两配对 + 从右往左合并"的两步法保证均摊 $O(\log n)$，decrease-key通过"剖出子树再合并"实现；
• 复杂度：全操作均为均摊复杂度，decrease-key的下界为 $\Omega(\log\log n)$，与斐波那契堆存在理论差距，但常数远优于它；
• 实践：竞赛中可直接使用__gnu_pbds::priority_queue的默认pairing_heap_tag，也可以在需要精细控制内存时参照本文代码手写实现。

配对堆是"以最简结构换最优实践效率"的数据结构典范，掌握其两步合并与 decrease-key 的剖离合并思想，对理解其他自调整数据结构（如 Splay 树）也有很大帮助。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki