1、Binomial heapIn computer science, a binomial heap is a heap similar to a binary heap but also supports quick merging of two heaps. This is achieved by using a special tree structure. It is important as an implementation of the mergeable heap abstract data type(also called meldable heap), which is a

2、priority queue supporting merge operation.Binomial tree A binomial heap is implemented as a collection of binomial trees (compare with a binary heap, which has a shape of a single binary tree). A binomial tree is defined recursively:· A binomial tree of order 0 is a single node· A binomial

3、 tree of order k has a root node whose children are roots of binomial trees of orders k1, k2, ., 2, 1, 0 (in this order).Binomial trees of order 0 to 3: Each tree has a root node with subtrees of all lower ordered binomial trees, which have been highlighted. For example, the order 3 binomial tree is

4、 connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.A binomial tree of order k has 2k nodes, height k.Because of its unique structure, a binomial tree of order k can be constructed from two trees of order k1 trivially by attaching one of them as the lef

5、tmost child of root of the other one. This feature is central to the merge operation of a binomial heap, which is its major advantage over other conventional heaps.The name comes from the shape: a binomial tree of order has nodes at depth . Structure of a binomial heap A binomial heap is implemented

6、 as a set of binomial trees that satisfy the binomial heap properties:· Each binomial tree in a heap obeys the minimum-heap property: the key of a node is greater than or equal to the key of its parent.· There can only be either one or zero binomial trees for each order, including zero ord

7、er.The first property ensures that the root of each binomial tree contains the smallest key in the tree, which applies to the entire heap.The second property implies that a binomial heap with n nodes consists of at most logn + 1 binomial trees. In fact, the number and orders of these trees are uniqu

8、ely determined by the number of nodes n: each binomial tree corresponds to one digit in the binary representation of number n. For example number 13 is 1101 in binary, , and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see figure below).Example of a

9、binomial heap containing 13 nodes with distinct keys.The heap consists of three binomial trees with orders 0, 2, and 3.Implementation Because no operation requires random access to the root nodes of the binomial trees, the roots of the binomial trees can be stored in a linked list, ordered by increa

10、sing order of the tree.Merge As mentioned above, the simplest and most important operation is the merging of two binomial trees of the same order within two binomial heaps. Due to the structure of binomial trees, they can be merged trivially. As their root node is the smallest element within the tre

11、e, by comparing the two keys, the smaller of them is the minimum key, and becomes the new root node. Then the other tree become a subtree of the combined tree. This operation is basic to the complete merging of two binomial heaps.function mergeTree(p, q)ifreturn p.addSubTree(q)elsereturn q.addSubTre

12、e(p)To merge two binomial trees of the same order, first compare the root key. Since 7>3, the black tree on the left(with root node 7) is attached to the grey tree on the right(with root node 3) as a subtree. The result is a tree of order 3.The operation of merging two heaps is perhaps the most i

13、nteresting and can be used as a subroutine in most other operations. The lists of roots of both heaps are traversed simultaneously, similarly as in the merge algorithmIf only one of the heaps contains a tree of order j, this tree is moved to the merged heap. If both heaps contain a tree of order j,

14、the two trees are merged to one tree of order j+1 so that the minimum-heap property is satisfied. Note that it may later be necessary to merge this tree with some other tree of order j+1 present in one of the heaps. In the course of the algorithm, we need to examine at most three trees of any order

15、(two from the two heaps we merge and one composed of two smaller trees).Because each binomial tree in a binomial heap corresponds to a bit in the binary representation of its size, there is an analogy between the merging of two heaps and the binary addition of the sizes of the two heaps, from right-

16、to-left. Whenever a carry occurs during addition, this corresponds to a merging of two binomial trees during the merge.Each tree has order at most log n and therefore the running time is O(log n).function merge(p, q)whilenot( p.end() and q.end() ) tree = mergeTree(p.currentTree(), q.currentTree()ifn

17、ot heap.currentTree().empty() tree = mergeTree(tree, heap.currentTree() heap.addTree(tree)else heap.addTree(tree) heap.next() p.next() q.next()This shows the merger of two binomial heaps. This is accomplished by merging two binomial trees of the same order one by one. If the resulting merged tree ha

18、s the same order as one binomial tree in one of the two heaps, then those two are merged again.Insert Insertinga new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Due to the merge, insert takes O(log n) time,howev

19、er it has an amortized time of O(1) (i.e. constant).Find minimum To find the minimumelement of the heap, find the minimum among the roots of the binomial trees. This can again be done easily in O(log n) time, as there are just O(log n) trees and hence roots to examine.By using a pointer to the binom

20、ial tree that contains the minimum element, the time for this operation can be reduced to O(1). The pointer must be updated when performing any operation other than Find minimum. This can be done in O(log n) without raising the running time of any operation.Delete minimum To delete the minimum eleme

21、nt from the heap, first find this element, remove it from its binomial tree, and obtain a list of its subtrees. Then transform this list of subtrees into a separate binomial heap by reordering them from smallest to largest order. Then merge this heap with the original heap. Since each tree has at mo

22、st log n children, creating this new heap is O(log n). Merging heaps is O(log n), so the entire delete minimum operation is O(log n).function deleteMin(heap) min = heap.trees().first()for each current in heap.trees()if current.root < min then min = currentfor each tree in min.subTrees() tmp.addTr

23、ee(tree) heap.removeTree(min) merge(heap, tmp)Decrease key After decreasingthe key of an element, it may become smaller than the key of its parent, violating the minimum-heap property. If this is the case, exchange the element with its parent, and possibly also with its grandparent, and so on, until

24、 the minimum-heap property is no longer violated. Each binomial tree has height at most log n, so this takes O(log n) time.Delete To deletean element from the heap, decrease its key to negative infinity (that is, some value lower than any element in the heap) and then delete the minimum in the heap.

25、Performance All of the following operations work in O(log n) time on a binomial heap with n elements:· Insert a new element to the heap· Find the element with minimum key· Delete the element with minimum key from the heap· Decrease key of a given element· Delete given elemen

26、t from the heap· Merge two given heaps to one heapFinding the element with minimum key can also be done in O(1) by using an additional pointer to the minimum.二項堆在計算機科學中，二項堆是一個二叉堆類似的堆結(jié)構(gòu)，但是支持兩個二項堆快速合并。這是通過使用一個特殊的樹結(jié)構(gòu)。實現(xiàn)可合并堆的抽象數(shù)據(jù)類型（也稱為meldable堆）是重要的，這個抽象數(shù)據(jù)結(jié)構(gòu)就是支持合并操作的優(yōu)先級隊列。二項樹二項堆是二項樹的集合（與二項堆相比二叉堆則只有

27、一顆二項樹）。二項式樹的遞歸定義： (1)0階二項樹是一個單一的節(jié)點 (2)k階二項樹有根訂單K-1，K-2，.，2，1，0（這個順序）二叉樹根節(jié)點的孩子。 上圖是0階到3階的二項樹：每一棵樹都有一個根節(jié)。連接在根節(jié)點上的是所有低階的子樹，這在圖中被高亮顯示。例如，3階二叉樹連接到2階，1和0（藍色，綠色和紅色高亮顯示）二叉樹。k階二項樹高度為K，共有2k個節(jié)點。由于其獨特的結(jié)構(gòu)，k階的二叉樹可以由兩棵k-1階的二叉樹構(gòu)成，通過將其中一棵二叉樹的根節(jié)點作為另外一棵二叉樹的最左子節(jié)點。這個特點對二叉堆的合并操作來說至關(guān)重要，這也是二項堆相對于傳統(tǒng)堆擁有的主要優(yōu)勢。二項樹的名字來源于形狀

28、：n階二叉樹在深度n處共有個節(jié)點。二項堆結(jié)構(gòu)二項式堆實現(xiàn)為一組滿足堆性質(zhì)的二項樹集合：(1)在堆的每二項式服從的最小堆屬性：一個節(jié)點的關(guān)鍵是大于或等于它的父鍵。 (2)任意階的二項樹只能有1個或者0個。包括0階二叉樹。第一屬性確保每個二叉樹的根包含樹中最小的鍵，它適用于整個堆中的二叉樹。第二個屬確保n個節(jié)點的二項堆最多包含lgn + 1棵二叉樹。事實上，二叉樹的數(shù)目和階數(shù)是由二叉堆的節(jié)點個數(shù)決定的：每顆二項樹和n的二進制表示中的一位對應(yīng)。例如13的二進制表示是1101，因此包含13個節(jié)點的二項堆包括三棵二叉樹 ，階數(shù)分別為3，2和0（見下圖）。實現(xiàn)因為沒有操作需要隨機訪問二叉樹的根節(jié)點，因此二

29、叉樹的根節(jié)點可以按照對應(yīng)階數(shù)的增序存儲在一個鏈表中。合并正如上面所提到的，最簡單的和最重要的操作是在兩個二叉堆中合并兩個階數(shù)相同的二叉樹。由于二叉樹的結(jié)構(gòu)，它們能夠被輕易的合并。由于二叉樹的根節(jié)點具有最小關(guān)鍵字，通過比較兩個根節(jié)點的關(guān)鍵字大小，其中較小的成為最小關(guān)鍵字，并成為新的根節(jié)點。另外一棵樹成為合并后的樹的一顆子樹。這個操作對于合并兩個二項堆而言是基礎(chǔ)的。function mergeTree(p, q)ifreturn p.addSubTree(q)elsereturn q.addSubTree(p) 對應(yīng)上圖，為了合并兩棵階數(shù)相同的二項樹，首先比較根節(jié)點的關(guān)鍵字。因為7>

30、; 3，在左邊的黑色樹（根節(jié)點7）連接到灰樹（與根結(jié)點3）右邊的子樹。結(jié)果是棵3階樹。合并兩個堆的操作也許是最有趣的，可以用來作為在大多數(shù)其他操作的子程序。和合并算法相似的是兩個二項堆的根節(jié)點鏈表同時被遍歷。如果只有一個堆包含j階的樹，這棵樹被移動到合并后的堆。如果兩個堆都包含j階的樹，兩棵樹被合并成一顆滿足最小堆性質(zhì)的階數(shù)為j+1的二叉樹。注意這棵樹以后也可能要和某個堆中j+1階的二叉樹合并。在算法的過程中，我們需要研究最三棵樹的任何順序的情況。因為二項堆中的每棵二項樹與表示二項堆大小的二進制表示中的一位對應(yīng)，合并兩個二項堆與兩個二進制數(shù)相加是相似的。由右至左，每當一個進位產(chǎn)生時都意味著兩棵二項樹的合并。每棵樹的階數(shù)不超過logn，因此運行時間是O（log n）的。 function merge(p, q)whilenot( p.end() and q.end() ) tree = mergeTree(p.currentTree(), q.currentTree()ifnot heap.currentTree().empty() tree = mergeTree(tree, heap.currentTree() heap.addTree(tree)else heap.addTree(tree) heap.n