二項式堆積

電腦科學中,二項式堆積(英語:Binomial heap)是一種類似於二元堆積堆結構。與二元堆積相比,其優勢是可以快速合併兩個堆,因此它屬於可合併堆(mergeable heap抽象資料類型的一種。

二項樹

二項樹遞迴定義如下:

  • 度數為0的二項樹只包含一個節點
  • 度數為k的二項樹有一個根節點,根節點下有 個子女,每個子女分別是度數分別為 的二項樹的根
 
二項樹(從左至右度數分別為0至3

度數為k的二項樹共有 個節點,高度為 。在深度d處有 二項式係數)個節點。

度數為k的二項樹可以很容易從兩顆度數為k-1的二項樹合併得到:把一顆度數為k-1的二項樹作為另一顆原度數為k-1的二項樹的最左子樹。這一性質是二項式堆積用於堆合併的基礎。

二項式堆積

二項式堆積是指滿足以下性質的二項樹的集合:

  • 每棵二項樹都滿足最小堆性質,即節點關鍵字大於等於其父節點的值
  • 不能有兩棵或以上的二項樹有相同度數(包括度數為0)。換句話說,具有度數k的二項樹有0個或1個。

以上第一個性質保證了二項樹的根節點包含了最小的關鍵字。第二個性質則說明節點數為 的二項式堆積最多只有   棵二項樹。實際上,包含n個節點的二項式堆積的構成情況,由n的二進制表示唯一確定,其中每一位對應於一顆二項樹。例如,13的二進制表示為1101,  , 因此具有13個節點的二項式堆積由度數為3, 2, 0的三棵二項樹組成:

 
範例:一個含13個節點的二項式堆積

二項式堆積的操作

由於並不需要對二項樹的根節點進行隨機存取,因而這些節點可以存成鏈結串列結構。

合併

 
合併分支度相同的二項樹
 
合併兩個二項式堆積範例,實際上把兩棵分支度為1的二項樹合併為一棵分支度為2的二項樹。

最基本的為二個分支度相同的二項樹的合併。由於二項樹根節點包含最小的關鍵字,因此在二棵樹合併時,只需比較二個根節點關鍵字的大小,其中含小關鍵字的節點成為結果樹的根節點,另一棵樹則變成結果樹的子樹。

function mergeTree(p, q)
    if p.root <= q.root
        return p.addSubTree(q)
    else
        return q.addSubTree(p)


兩個二項式堆積的合併則可按如下步驟進行:分支度 從小取到大,在兩個二項式堆積中如果其中只有一棵樹的分支度為 ,即將此樹移動到結果堆,而如果只兩棵樹的分支度都為 ,則根據以上方法合併為一個分支度為 的二項樹。此後這個分支度為 的樹將可能會和其他分支度為 的二項樹進行合併。因此,對於任何分支度j,可能最多需要合併3棵二項樹。

此操作的時間複雜度為 

function merge(p, q)
    while not (p.end() and q.end())
        tree = mergeTree(p.currentTree(), q.currentTree())
        
        if not heap.currentTree().empty()
            tree = mergeTree(tree, heap.currentTree())
        
        heap.addTree(tree)
        heap.next(); p.next(); q.next()

插入

建立一個只包含要插入元素的二項式堆積,再將此堆與原先的二項式堆積進行合併,即可得到插入後的堆。由於需要合併,插入操作需要 的時間。平攤分析的時間複雜度為 

尋找最小關鍵字所在節點

由於滿足最小堆性質,只需尋找二項樹的的根節點即可,因為一共有 棵子樹,所以用所時間為 

可以儲存一個指向最小元素的指標,使得尋找最小關鍵字所在節點需要 的時間。在執行其他操作時,需要修改該指標。

刪除最小關鍵字所在節點

先找到最小關鍵字所在節點,然後將它從其所在的二項樹中刪除,並獲得其子樹。將這些子樹看作(合併為)一個獨立的二項式堆積,再將此堆合併到原先的堆中即可。由於每棵樹最多有 棵子樹,新增堆的時間為 。同時合併堆的時間也為 ,故整個操作所需時間為 

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

減小特定節點(關鍵字)的值(Decreasing a key)

在減小特定節點(關鍵字)的值後,可能會不滿足最小堆積性質。此時,將其所在節點與父節點交換,如還不滿足最小堆性質則再與祖父節點交換……直到最小堆性質得到滿足。操作所需時間為 

刪除

將需要刪除的節點的關鍵字的值減小到負無窮大(比二項式堆積中的其他所有關鍵字的值都小即可),執行「減小關鍵字的值」演算法,使其調整到當前二項樹的根節點位置,再刪除最小關鍵字的根節點即可。

執行時間

以下對於二項式堆積操作的執行時間都為 (節點數為 ):

  • 在二項式堆積中插入新節點
  • 尋找最小關鍵字所在節點
  • 從二項式堆積中刪除最小關鍵字所在節點
  • 減小給定節點關鍵字的值
  • 刪除給定節點
  • 合併兩個二項式堆積

參見

參考資料

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein(潘金貴等譯). 《算法导论》. 機械工業出版社. 
  • Vuillemin, J. (1978). A data structure for manipulating priority queues. Communications of the ACM 21, 309–314.

外部連結