成對堆的變體

成對堆可以是空堆，或者是由根元素和一個可能為空的成對樹清單組成的成對樹。

堆排序屬性需要任何節點的父節點都不大於該節點本身。

以下說明考慮了一個純粹的功能性堆，它不支援 decrease-key 操作。

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

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

成對堆有兩種形式——最小成對堆和最大成對堆。當我們要表示最小優先順序佇列時，會實現最小成對堆，而當要實現最大優先順序佇列時，會實現最大成對堆。根據我們在文字中對堆和左斜樹的討論，我們在這裡明確討論最大成對堆。最小成對堆可以類比。

最大成對堆被定義為一個最大樹。

下面顯示了四個最大成對堆。請注意，成對堆不需要是二叉樹。

Arnab Chakraborty

更新於: 2020 年 1 月 2 日

141 次瀏覽

開啟您的 職業生涯

完成課程以獲得認證

開始使用