二項堆

堆（Heap）是計算機科學中一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹的數組對象。二項堆（binomial heap）是一種類似於二叉堆的堆結構。與二叉堆相比，其優勢是可以快速合併兩個堆，因此它屬於可合併堆（mergeable heap）抽象數據類型的一種。

基本介紹

• 中文名：二項堆
• 外文名：binomial heap
• 領域：數據結構
• 定義：一種類似於二叉堆的堆結構
• 組成：二項樹
• 套用：用於實現合併優先佇列

定義

二項堆是是二項樹的集合或是由一組二項樹組成。二項堆具有良好的性質。在 的時間內即可完成兩個二項堆合併操作，所以二項堆是可合併堆，而僅僅需要 的時間，二項堆即可完成插入操作。因此，基於二項堆實現的優先佇列和進程調度算法有著很好的時間性能。同時由於二項樹的結構特性和性質，二項樹在網路最佳化等諸多領域也套用廣泛。

二項樹

二項樹是一種遞歸定義的有序樹，二項樹遞歸定義如下：

1、度數為0的二項樹只包含一個結點。

2、度數為k的二項樹有一個根結點，根結點下有 個子女，每個子女分別是度數分別為 的二項樹的根。

度數為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)

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

刪除

將需要刪除的結點的關鍵字的值減小到負無窮大（比二項堆中的其他所有關鍵字的值都小即可），執行“減小關鍵字的值”算法，使其調整到當前二項樹的根節點位置，再刪除最小關鍵字的根結點即可。

Python實現

""" BinomialQueue.py Meldable priority queues Written by Gregoire Dooms and Irit Katriel"""class LinkError(Exception): passclass EmptyBinomialQueueError(Exception): passclass BinomialTree:    "A single Binomial Tree"    def __init__(self, value):        "Create a one-node tree. value is the priority of this node"        self.value = value          self.rank = 0        self.children = []    def link(self, other_tree):        """Make other_tree the son of self. Both trees must have the        same rank, and other_tree must have a larger minimum priority        """        if self.rank != other_tree.rank:            raise LinkError()        if self.value > other_tree.value:            raise LinkError()        self.children.append(other_tree)        self.rank += 1         return True    def str(self, indent = 0):        return (" "*indent +                "rank: %d value: %d"%(self.rank, self.value)+                "\n"+"".join(child.str(indent+2)                             for child in self.children)               )        def __str__(self):        return self.str()        class BinomialQueue:    """  A Meldable priority Queue """    def __init__(self,infinity=1e300):        """        Create an empty Binomial Queue.        Since a queue can hold any comparable data type, we need to know        at initialization time what an "infinity" element looks like.        """        self.infinity = infinity        self.parent = self        self.trees = []        self.elements = 0                self.min = self.infinity        self.min_tree_rank = -1    def __capacity(self):        return 2**len(self.trees) - 1    def __resize(self):        while self.__capacity() < self.elements:            self.trees.append(None)    def __add_tree(self,new_tree):        " Insert new_tree into self"        self.elements = self.elements + 2**new_tree.rank        self.__resize()        while self.trees[new_tree.rank] is not None:            if self.trees[new_tree.rank].value < new_tree.value:                new_tree, self.trees[new_tree.rank] = \                 self.trees[new_tree.rank], new_tree     # swap            r = new_tree.rank            new_tree.link(self.trees[r])            self.trees[r] = None        self.trees[new_tree.rank] = new_tree        if new_tree.value <= self.min:            self.min = new_tree.value            self.min_tree_rank = new_tree.rank            def meld(self, other_queue):        "Insert all elements of other_queue into self "        for tree in other_queue.trees:            if tree is not None:                self.__add_tree(tree)    def insert(self, value):        "Insert value into self "        tree = BinomialTree(value)                self.__add_tree(tree)    def get_min(self):        "Return the minimum element in self"        return self.min    def delete_min(self):        "Delete the minumum element from self "        if not self:            raise EmptyBinomialQueueError()        to_remove = self.trees[self.min_tree_rank]     self.trees[to_remove.rank] = None        self.elements = self.elements - 2**to_remove.rank                for child in to_remove.children:            self.__add_tree(child)                    self.min = self.infinity        for tree in self.trees:            if tree is not None:                if tree.value <= self.min:                    self.min = tree.value                    self.min_tree_rank = tree.rank                         def __nonzero__(self):        return self.elements    def __str__(self):        s = """elements: %d min: %s        min_tree_rank: %d        tree vector: """ % (self.elements, str(self.min), self.min_tree_rank)        s += " ".join("10"[tree is None] for tree in self.trees)        s += "\n"        s += "".join(str(tree) for tree in self.trees if tree is not None)        return s        def __len__(self):        return self.elements        def __iadd__(self,other):        if type(other) == type(self):            self.meld(other)        else:            self.insert(other)        return self                def run_test():    inf = 2e300    N = 10    Q1 = BinomialQueue(inf)    Q2 = BinomialQueue(inf)            print Q1        print "-------------------------------------------"            Q1 += 20  # Same as  Q1.insert(20)    Q1.insert(1)        Q1.insert(5)    Q1.insert(10)    print Q1    print "-------------------------------------------"            Q2.insert(2)    Q2.insert(22)    Q2.insert(12)    print Q2    print "-------------------------------------------"            Q1 += Q2   # Same as  Q1.meld(Q2)    print Q1    print "-------------------------------------------"                while Q1:        print "Q1.min = ", Q1.min        Q1.delete_min()if __name__ == "__main__":    run_test()