成对堆的变体

成对堆可以是空堆，或者是由根元素和一个可能为空的成对树清单组成的成对树。

堆排序属性需要任何节点的父节点都不大于该节点本身。

以下说明考虑了一个纯粹的功能性堆，它不支持 decrease-key 操作。

type PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]])

type PairingHeap[Element] = Empty | PairingTree[Element]

成对堆有两种形式——最小成对堆和最大成对堆。当我们要表示最小优先级队列时，会实现最小成对堆，而当要实现最大优先级队列时，会实现最大成对堆。根据我们在文本中对堆和左斜树的讨论，我们在这里明确讨论最大成对堆。最小成对堆可以类比。

最大成对堆被定义为一个最大树。

下面显示了四个最大成对堆。请注意，成对堆不需要是二叉树。

Arnab Chakraborty

更新于: 2020 年 1 月 2 日

141 次浏览

开启您的 职业生涯

完成课程以获得认证

开始使用