配对堆

$$\Theta(1)$$ 配对堆（Pairing heap）是一种实现简单、均摊复杂度优越的堆数据结构，由迈克尔·弗雷德曼、罗伯特·塞奇威克、丹尼尔·斯莱托、罗伯特·塔扬于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)$。

$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'''
```

## 外部链接

- Louis Wasserman discusses pairing heaps and their implementation in Haskell in The Monad Reader, Issue 16 (pp. 37–52).
- pairing heaps , Sartaj Sahni

## 基本资料

- 类型：堆积
- 搜索：迈克尔·弗雷德曼、罗伯特·塞奇威克、丹尼尔·斯莱托、罗伯特·塔扬
- 算法：1986年
- insert_avg：$\Theta(1)$
- delete_min_avg：$O(\log n)$
- delete_min_worst：&nbsp
- find_min_avg：$\Theta(1)$
- find_min_worst：&nbsp
- decrease_key_avg：$O(\log n)$
- merge_avg：$\Theta(1)$
- merge_worst：&nbsp