配对堆

配对堆是一种堆数据结构，实现相对容易，并且具有极佳的实际平均性能。

配对堆是堆有序的多路树结构，可以看作简化的斐波那契堆。

它们被认为是实现诸如 Prim 最小生成树算法等算法的“可靠选择”，并支持以下操作（假设为最小堆）：

  • 查找最小值 (find-min) - 此函数负责返回堆的顶部元素。
  • 合并 (meld) - 此函数负责比较两个根元素，较小的元素保持为结果的根，较大的元素及其子树作为此根的子节点添加。
  • 插入 (insert) - 此函数负责为插入的元素创建一个新的堆，并将其合并到原始堆中。
  • 减小键值 (decrease-key, 可选) - 此函数负责移除以要减小的键为根的子树，用较小的键替换该键，然后将结果合并回堆中。
  • 删除最小值 (delete-min) - 此函数负责移除根节点，并对其子树进行重复合并，直到只剩下一个树。
  • 每个节点都有一个指向左孩子的指针，左孩子指向该孩子的下一个兄弟节点。
  • 配对堆示例如下：

配对堆的时间复杂度分析主要受到伸展树的启发。删除最小值操作的平均时间复杂度被认为是 O(log n)，而查找最小值、合并和插入操作的平均时间复杂度为 O(1)。

更新于：2020年1月2日

692 次浏览

开启您的职业生涯

完成课程获得认证

开始学习
广告