配对堆

**配對堆**是一種實現簡單、均攤複雜度優越的堆資料結構，由邁克爾・弗雷德曼、羅伯特・塞奇威克、丹尼爾・斯萊托、羅伯特・塔揚於 1986 年發明。
配對堆是一種多叉樹，並且可以被認為是一種簡化的斐波那契堆。對於實現例如普林姆最小生成樹算法等算法，配對堆是一個更優的選擇，且支持以下操作（假設該堆是最小堆）：

* _find-min_（查找最小值）：返回堆頂。
* _merge_（合併）：比較兩個堆頂，將堆頂較大的堆設為另一個的孩子。
* _insert_（插入）：創建一個只有一個元素的堆，並合併至原堆中。
* _decrease-key_（減小元素）（可選）：將以該節點為根的子樹移除，減小其權值，並合併回去。
* _delete-min_（刪除最小值）：刪除根並將其子樹合併至一起。這裡有各種不同的方式。

配對堆時間複雜度的分析靈感來源於伸展樹。
其 _delete-min_ 操作的時間複雜度為 _O_(log _n_)，而 _find-min_、_merge_ 和 _insert_ 操作的均攤時間複雜度均為 _O_(1)。

確定配對堆每次進行 _decrease-key_ 操作的均攤時間複雜度是困難的。最初，基於經驗，這個操作的時間複雜度被推測為是 _O_(1)，但弗雷德曼證明了對於某些操作序列，每次 _decrease-key_ 操作的時間複雜度至少為 $\Omega (\log \log n)$ 。
在那之後，通過不同的均攤依據，Pettie 證明了 _insert_、_merge_ 及 _decrease-key_ 操作的均攤時間複雜度均為 $O(2^{2{\sqrt {\log \log n}}})$ ，近似於 $o(\log n)$ 。
Elmasry 後來介紹了一種配對堆的變體，令其擁有所有斐波那契堆可以實現的操作，且 _decrease-key_ 操作的均攤時間複雜度為 $O(\log \log n)$ ，但對於原始的資料結構，仍未知準確的 $\Theta (\log \log n)$ 運行下限。此外，能否使 _delete-min_ 在均攤時間複雜度為 $o(\log n)$ 的同時，令 _insert_ 操作的均攤時間複雜度為 $O(1)$ ，目前也仍未得到解決。

儘管這比其他的，例如能實現均攤時間 $O(1)$ 的 _decrease-key_ 的斐波那契堆，這樣的優先隊列算法更差，在實踐中配對堆的表現仍然很不錯。Stasko 和 Vitter，
Moret 和 Shapiro，
以及 Larkin、Sen 和 Tarjan
進行過配對堆和其他堆資料結構的實驗。 他們得出的結論是，配對堆通常比基於數組的二叉堆和 D 叉堆的實際操作速度更快，而且在實踐中幾乎總是比其他基於指針的堆更快，其中包括諸如斐波納契堆這樣的理論上更有效率的資料結構。

## 結構

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

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

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

## 操作

### find-min（查找最小值）

函數 _find-min_ 簡單地返回該堆的堆頂：

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

 

### merge（合併）

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

```
**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)
```

### insert（插入）

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

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

 

### delete-min（刪除最小值）

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

```
**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..]))
```

這確實實現了所描述的兩個通過從左向右、然後從右向左的合併策略。這可以下面的過程看到：

```
   merge-pairs([H1, H2, H3, H4, H5, H6, H7])
=> merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7]))
     # 合并H1和H2到H12，再处理列表中剩下的部分
=> merge(**H12**, merge(merge(H3, H4), merge-pairs([H5, H6, H7])))
     # 合并H3和H4到H34，再处理列表中剩下的部分
=> merge(H12, merge(**H34**, merge(merge(H5, H6), merge-pairs([H7]))))
     # 合并H5和H6到H56，再处理列表中剩下的部分
=> merge(H12, merge(H34, merge(**H56**, H7)))
     # 转换方向，合并最后两个堆，给出H567
=> merge(H12, merge(H34, **H567**))
     # 合并最后两个堆，给出H34567
=> merge(H12, **H34567**) 
     # 最终，合并第一个堆和剩下堆合并的结果
=> **H1234567**
```

## 運行時間統計

下面的時間複雜度中，_O_(_f_) 是一個漸近的上界，而 _Θ_(_f_) 是一個準確的上界（見大 O 符號）。函數名均假設該堆為最小堆。

## 參考文獻

## 外部連結

* Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 （頁面存檔備份，存於網際網路檔案館） (pp. 37–52).
* pairing heaps （頁面存檔備份，存於網際網路檔案館）, Sartaj Sahni