配对堆(Pairing Heap)

配对堆是一种基于多叉树的可合并堆,以实现简单和实测性能出色而闻名。它把合并作为最基本的操作,插入、取最小值都建立在合并之上,被认为是斐波那契堆在工程实践中的高效替身。

概述

配对堆由弗雷德曼、塞奇威克、斯利特与塔扬于1986年提出。整个堆是一棵满足堆序的多叉树,用左孩子右兄弟的方式存储。它没有斐波那契堆那样繁琐的度数标记与级联剪切逻辑,代码量小,常数因子低,因此在竞赛与实际系统中被广泛采用。

核心原理

• 合并:比较两个根,把较大者作为较小者的第一个孩子,是唯一真正的结构原语。
• 插入:视为与单节点堆合并。
• 删除最小值:去掉根后,把其众多孩子按两两配对再从右向左依次合并,这一步决定了整体效率。
• 减小键值:把该子树从原位置剪下,再与整棵堆合并。

应用场景

配对堆常用于需要频繁减键的图算法,如迪杰斯特拉最短路和普里姆最小生成树,是斐波那契堆的实用替代。在算法竞赛中,它常被用来维护可合并的优先队列。许多语言的高性能库也采用其变体作为默认可并堆实现。

常见问题

问:配对堆的减键操作精确复杂度是多少?答:这至今仍是未完全解决的理论难题;已知它介于常数与对数之间,实测通常接近常数,但严格的紧界证明相当困难。

问:配对堆和斐波那契堆该选哪个?答:工程上多数情况选配对堆,因为它实现简单、缓存友好、常数小;斐波那契堆主要在追求理论最优摊还界时使用。