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)$。为了保住均摊复杂度必须采用**两步走合并方法**第一步配对把儿子们两两配成一对用meld把配成同一对的两个儿子合并到一起第二步从右往左合并将新产生的堆从右往左即从老的儿子到新的儿子的方向挨个合并在一起。先实现辅助函数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)); // 核心部分 }最后一行是该函数的核心它由三部分组成meld(x, y)配对了 x 和 ymerges(c)递归合并 c 和它的兄弟们将上面两个操作产生的两个新树合并。这里特别提醒第二步的合并方向必须是从右往左该递归实现已经天然保证了这一顺序。如果读者要自行编写迭代版本请务必注意保持从右往左的顺序否则复杂度将失去保证。有了mergesdelete-min的实现就顺理成章了Node* delete_min(Node* x) { Node* t merges(x-child); delete x; // 如果需要内存回收 return t; }减小一个元素的值decrease-keydecrease-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-keyImproved upper bounds for pairing heaps以及 Pettie 给出的 $O(2^{2\sqrt{\log\log n}})$meld和decrease-keyTowards 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分别是Tag特点pairing_heap_tag配对堆官方文档认为在非原生元素自定义结构体、std::string、pair等中表现最好binary_heap_tag二叉堆官方认为在原生元素中表现最好binomial_heap_tag二项堆合并优于二叉堆但取堆顶复杂度更高rc_binomial_heap_tag冗余计数二项堆thin_heap_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_queueint::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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 OI-wiki 配对堆（Pairing Heap）详解：自调整可并堆的结构、实现与复杂度分析
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)$。为了保住均摊复杂度必须采用**两步走合并方法**第一步配对把儿子们两两配成一对用meld把配成同一对的两个儿子合并到一起第二步从右往左合并将新产生的堆从右往左即从老的儿子到新的儿子的方向挨个合并在一起。先实现辅助函数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)); // 核心部分 }最后一行是该函数的核心它由三部分组成meld(x, y)配对了 x 和 ymerges(c)递归合并 c 和它的兄弟们将上面两个操作产生的两个新树合并。这里特别提醒第二步的合并方向必须是从右往左该递归实现已经天然保证了这一顺序。如果读者要自行编写迭代版本请务必注意保持从右往左的顺序否则复杂度将失去保证。有了mergesdelete-min的实现就顺理成章了Node* delete_min(Node* x) { Node* t merges(x-child); delete x; // 如果需要内存回收 return t; }减小一个元素的值decrease-keydecrease-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-keyImproved upper bounds for pairing heaps以及 Pettie 给出的 $O(2^{2\sqrt{\log\log n}})$meld和decrease-keyTowards 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分别是Tag特点pairing_heap_tag配对堆官方文档认为在非原生元素自定义结构体、std::string、pair等中表现最好binary_heap_tag二叉堆官方认为在原生元素中表现最好binomial_heap_tag二项堆合并优于二叉堆但取堆顶复杂度更高rc_binomial_heap_tag冗余计数二项堆thin_heap_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_queueint::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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考