[科普中國(guó)]-配對(duì)堆

配對(duì)堆是一種實(shí)現(xiàn)簡(jiǎn)單、均攤復(fù)雜度優(yōu)越的堆數(shù)據(jù)結(jié)構(gòu)，由Michael Fredman、羅伯特·塞奇威克、Daniel Sleator、羅伯特·塔揚(yáng)于1986年發(fā)明。配對(duì)堆是一種多叉樹，并且可以被認(rèn)為是一種簡(jiǎn)化的斐波那契堆。對(duì)于實(shí)現(xiàn)例如普林姆最小生成樹算法等算法，配對(duì)堆是一個(gè)更優(yōu)的選擇，

結(jié)構(gòu)一個(gè)配對(duì)堆要么是一個(gè)空堆，要么就是一個(gè)配對(duì)樹，由一個(gè)根元素與一個(gè)可能為空的配對(duì)樹列表所組成。堆的有序?qū)傩允乖摿斜碇兴凶訕涞母囟疾恍∮谠摱训母?。下面描述了一個(gè)純粹的函數(shù)堆，我們假定它不支持decrease-key操作。

type PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]])type PairingHeap[Elem] = Empty | PairingTree[Elem]對(duì)于隨機(jī)存取機(jī)，一個(gè)基于指針的實(shí)現(xiàn)若要支持decrease-key操作，可以對(duì)每個(gè)節(jié)點(diǎn)使用三個(gè)指針做到，具體做法是用單向鏈表儲(chǔ)存節(jié)點(diǎn)的孩子：一個(gè)指針指向該節(jié)點(diǎn)的第一個(gè)孩子，一個(gè)指向它的下個(gè)兄弟，一個(gè)指向它的上個(gè)兄弟（對(duì)于最左邊的兄弟則指向它的父親）。或者，如果使用一個(gè)布爾標(biāo)記表示“鏈表末尾”且令最后一個(gè)孩子指向它的父親，指向上個(gè)兄弟的指針也可以不使用。這在犧牲常數(shù)開銷的同時(shí)，令結(jié)構(gòu)更加緊湊。

操作查找最小值函數(shù)find-min簡(jiǎn)單地返回該堆的堆頂：

function find-min(heap: PairingHeap[Elem]) -> Elem if heap is Empty error else return heap.elem合并合并一個(gè)空堆將會(huì)返回另一個(gè)堆，否則將會(huì)返回一個(gè)新堆，其將兩個(gè)堆的根元素中較小的元素當(dāng)作新堆的根元素，并將較大的元素所在的堆合并到新堆的子堆中：1

function merge(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem] if heap1 is Empty return heap2 elsif heap2 is Empty return heap1 elsif heap1.elem PairingHeap[Elem] return merge(Heap(elem, []), heap)刪除最小值比較復(fù)雜的操作即是堆中最小值的刪除操作。標(biāo)準(zhǔn)方法是：首先將子堆從左到右、一對(duì)一對(duì)地合并（這就是它叫這個(gè)名字的原因），然后再?gòu)挠业阶蠛喜⒃摱选?

function delete-min(heap: PairingHeap[Elem]) -> PairingHeap[Elem] if heap is Empty error else return merge-pairs(heap.subheaps)這需要使用到輔助函數(shù)merge-pairs（合并對(duì)）：

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..]))這確實(shí)實(shí)現(xiàn)了所描述的兩個(gè)通過從左向右、然后從右向左的合并策略。這可以下面的過程看到：

merge-pairs([H1, H2, H3, H4, H5, H6, H7]) => merge(merge(H1, H2), merge-pairs([H3, H4, H5, H6, H7]))=> merge(H12, merge(merge(H3, H4), merge-pairs([H5, H6, H7]))) => merge(H12, merge(H34, merge(merge(H5, H6), merge-pairs([H7])))) => merge(H12, merge(H34, merge(H56, H7))) => merge(H12, merge(H34, H567))=> merge(H12, H34567) # 最終，合并第一個(gè)堆和剩下堆合并的結(jié)果 => H1234567本詞條內(nèi)容貢獻(xiàn)者為:

王慧維 - 副研究員 - 西南大學(xué)