配對堆

結構

一個配對堆要么是一個空堆，要么就是一個配對樹，由一個根元素與一個可能為空的配對樹列表所組成。堆的有序屬性使該列表中所有子樹的根元素都不小於該堆的根元素。下面描述了一個純粹的函式堆，我們假定它不支持decrease-key操作。

type PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]])type PairingHeap[Elem] = Empty | PairingTree[Elem]

對於隨機存取機，一個基於指針的實現若要支持decrease-key操作，可以對每個節點使用三個指針做到，具體做法是用單向鍊表儲存節點的孩子：一個指針指向該節點的第一個孩子，一個指向它的下個兄弟，一個指向它的上個兄弟（對於最左邊的兄弟則指向它的父親）。或者，如果使用一個布爾標記表示“鍊表末尾”且令最後一個孩子指向它的父親，指向上個兄弟的指針也可以不使用。這在犧牲常數開銷的同時，令結構更加緊湊。

操作

查找最小值

函式find-min簡單地返回該堆的堆頂：

function find-min(heap: PairingHeap[Elem]) -> Elem  if heap is Empty    error  else   return heap.elem

合併

合併一個空堆將會返回另一個堆，否則將會返回一個新堆，其將兩個堆的根元素中較小的元素當作新堆的根元素，並將較大的元素所在的堆合併到新堆的子堆中：

function merge(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem]  if heap1 is Empty    return heap2  elsif heap2 is Empty      return heap1  elsif heap1.elem   < heap2.elem            return Heap(heap1.elem, heap2 :: heap1.subheaps)            else  return Heap(heap2.elem, heap1 :: heap2.subheaps)

插入

插入一個元素最簡單的方法是，將一個僅有該元素的新堆與需要被插入的堆合併：

function insert(elem: Elem, heap: PairingHeap[Elem]) ->       PairingHeap[Elem]     return merge(Heap(elem, []), heap)

刪除最小值

比較複雜的操作即是堆中最小值的刪除操作。標準方法是：首先將子堆從左到右、一對一對地合併（這就是它叫這個名字的原因），然後再從右到左合併該堆。

function delete-min(heap: PairingHeap[Elem]) ->       PairingHeap[Elem]  if heap is Empty    error        else    return merge-pairs(heap.subheaps)

這需要使用到輔助函式merge-pairs（合併對）：

function merge-pairs(list: List[PairingTree[Elem]]) ->       PairingHeap[Elem] if length(list) == 0            return Empty  elsif length(list) == 1    return list[0]             else   return merge(merge(list[0], list[1]), merge-pairs(list[2..]))

配對堆

基本介紹

結構

操作

查找最小值

合併

插入

刪除最小值

相關詞條

熱門詞條