計算機科學(xué)外文翻譯

1、<p>　　Binomial heap</p><p>　　In 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

2、is important as an implementation of the mergeable heap abstract data type(also called meldable heap), which is a priority queue supporting merge operation.</p><p>　　Binomial tree </p><p>　　A bi

3、nomial 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:</p><p>　　A binomial tree of order

4、 0 is a single node</p><p>　　A binomial tree of order k has a root node whose children are roots of binomial trees of orders k?1, k?2, ..., 2, 1, 0 (in this order).</p><p>　　Binomial trees of or

5、der 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 connected to an order 2, 1, and 0 (highlighted as blue, gree

6、n and red respectively) binomial tree.</p><p>　　A binomial tree of order k has 2k nodes, height k.</p><p>　　Because of its unique structure, a binomial tree of order k can be constructed from tw

7、o trees of order k?1 trivially by attaching one of them as the leftmost 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 conventio

8、nal heaps.</p><p>　　The name comes from the shape: a binomial tree of order has nodes at depth . </p><p>　　Structure of a binomial heap </p><p>　　A binomial heap is implemented as

9、a set of binomial trees that satisfy the binomial heap properties:</p><p>　　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.&

10、lt;/p><p>　　There can only be either one or zero binomial trees for each order, including zero order.</p><p>　　The first property ensures that the root of each binomial tree contains the smallest k

11、ey in the tree, which applies to the entire heap.</p><p>　　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 t

12、rees are uniquely 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 nod

13、es will consist of three binomial trees of orders 3, 2, and 0 (see figure below).</p><p>　　Example of a binomial heap containing 13 nodes with distinct keys.The heap consists of three binomial trees with or

14、ders 0, 2, and 3.</p><p>　　Implementation </p><p>　　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

15、 list, ordered by increasing order of the tree.</p><p><b>　　Merge </b></p><p>　　As mentioned above, the simplest and most important operation is the merging of two binomial trees of

16、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 tree, by comparing the two keys, the smaller of them i

17、s 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</p><p>　　function mergeTree(

18、p, q)</p><p>　　if p.root.key <= q.root.key</p><p>　　return p.addSubTree(q)</p><p><b>　　else</b></p><p>　　return q.addSubTree(p)</p><p>　　To

19、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

20、 tree of order 3.</p><p>　　The operation of merging two heaps is perhaps the most interesting and can be used as a subroutine in most other operations. The lists of roots of both heaps are traversed simultan

21、eously, similarly as in the merge algorithm</p><p>　　If 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, the two trees are mer

22、ged 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 algo

23、rithm, we need to examine at most three trees of any order (two from the two heaps we merge and one composed of two smaller tr</p><p>　　Because each binomial tree in a binomial heap corresponds to a bit in t

24、he 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-to-left. Whenever a carry occurs during addition, this correspo

25、nds to a merging of two binomial trees during the merge.</p><p>　　Each tree has order at most log n and therefore the running time is O(log n).</p><p>　　function merge(p, q)</p><p>

26、　　while not( p.end() and q.end() )</p><p>　　tree = mergeTree(p.currentTree(), q.currentTree())</p><p>　　if not heap.currentTree().empty()</p><p>　　tree = mergeTree(tree, heap.curren

27、tTree())</p><p>　　heap.addTree(tree)</p><p><b>　　else</b></p><p>　　heap.addTree(tree)</p><p>　　heap.next() p.next() q.next()</p><p>　　This show

28、s 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 has the same order as one binomial tree in one of the two heaps, then thos

29、e two are merged again.</p><p><b>　　Insert </b></p><p>　　Inserting a new element to a heap can be done by simply creating a new heap containing only this element and then merging it

30、with the original heap. Due to the merge, insert takes O(log n) time, however it has an amortized time of O(1) (i.e. constant).</p><p>　　Find minimum </p><p>　　To find the minimum element of the

31、 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.</p><p>　　By using a pointer to the

32、binomial 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

33、 raising the running time of any operation.</p><p>　　Delete minimum </p><p>　　To delete the minimum element from the heap, first find this element, remove it from its binomial tree, and obtain a

34、 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 most log n

35、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).</p><p>　　function deleteMin(heap)</p><p>　　min = heap.trees().first()

36、</p><p>　　for each current in heap.trees()</p><p>　　if current.root < min then min = current</p><p>　　for each tree in min.subTrees()</p><p>　　tmp.addTree(tree)</

37、p><p>　　heap.removeTree(min)</p><p>　　merge(heap, tmp)</p><p>　　Decrease key </p><p>　　After decreasing the key of an element, it may become smaller than the key of its pa

38、rent, 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 the minimum-heap property is no longer violated. Each binomia

39、l tree has height at most log n, so this takes O(log n) time.</p><p><b>　　Delete </b></p><p>　　To delete an element from the heap, decrease its key to negative infinity (that is, som

40、e value lower than any element in the heap) and then delete the minimum in the heap.</p><p>　　Performance </p><p>　　All of the following operations work in O(log n) time on a binomial heap with

41、n elements:</p><p>　　Insert a new element to the heap</p><p>　　Find the element with minimum key</p><p>　　Delete the element with minimum key from the heap</p><p>　　Dec

42、rease key of a given element</p><p>　　Delete given element from the heap</p><p>　　Merge two given heaps to one heap</p><p>　　Finding the element with minimum key can also be done in

43、 O(1) by using an additional pointer to the minimum.</p><p><b>　　二項堆</b></p><p>　　在計算機科學(xué)中，二項堆是一個二叉堆類似的堆結(jié)構(gòu)，但是支持兩個二項堆快速合并。這是通過使用一個特殊的樹結(jié)構(gòu)。實現(xiàn)可合并堆的抽象數(shù)據(jù)類型（也稱為meldable堆）是重要的，這個抽象數(shù)據(jù)結(jié)構(gòu)就是支持合并操

44、作的優(yōu)先級隊列。</p><p><b>　　二項樹</b></p><p>　　二項堆是二項樹的集合（與二項堆相比二叉堆則只有一顆二項樹）。二項式樹的遞歸定義： (1)0階二項樹是一個單一的節(jié)點 (2)k階二項樹有根訂單K-1，K-2，...，2，1，0（這個順序）二叉樹根節(jié)點的孩子。</p><p>　　上圖是0階到

45、3階的二項樹：每一棵樹都有一個根節(jié)。連接在根節(jié)點上的是所有低階的子樹，這在圖中被高亮顯示。例如，3階二叉樹連接到2階，1和0（藍色，綠色和紅色高亮顯示）二叉樹。</p><p>　　k階二項樹高度為K，共有2k個節(jié)點。</p><p>　　由于其獨特的結(jié)構(gòu)，k階的二叉樹可以由兩棵k-1階的二叉樹構(gòu)成，通過將其中一棵二叉樹的根節(jié)點作為另外一棵二叉樹的最左子節(jié)點。這個特點對二叉堆的合并操作來說

46、至關(guān)重要，這也是二項堆相對于傳統(tǒng)堆擁有的主要優(yōu)勢。</p><p>　　二項樹的名字來源于形狀：n階二叉樹在深度n處共有個節(jié)點。</p><p><b>　　二項堆結(jié)構(gòu)</b></p><p>　　二項式堆實現(xiàn)為一組滿足堆性質(zhì)的二項樹集合：</p><p>　　(1)在堆的每二項式服從的最小堆屬性：一個節(jié)點的關(guān)鍵是大于或

47、等于它的父鍵。 (2)任意階的二項樹只能有1個或者0個。包括0階二叉樹。</p><p>　　第一屬性確保每個二叉樹的根包含樹中最小的鍵，它適用于整個堆中的二叉樹。第二個屬確保n個節(jié)點的二項堆最多包含lgn + 1棵二叉樹。事實上，二叉樹的數(shù)目和階數(shù)是由二叉堆的節(jié)點個數(shù)決定的：每顆二項樹和n的二進制表示中的一位對應(yīng)。例如13的二進制表示是1101，因此包含13個節(jié)點的二項堆包括三棵二叉樹 ，階數(shù)分別為

48、3，2和0（見下圖）。</p><p><b>　　實現(xiàn)</b></p><p>　　因為沒有操作需要隨機訪問二叉樹的根節(jié)點，因此二叉樹的根節(jié)點可以按照對應(yīng)階數(shù)的增序存儲在一個鏈表中。</p><p><b>　　合并</b></p><p>　　正如上面所提到的，最簡單的和最重要的操作是在兩個二叉

49、堆中合并兩個階數(shù)相同的二叉樹。由于二叉樹的結(jié)構(gòu)，它們能夠被輕易的合并。由于二叉樹的根節(jié)點具有最小關(guān)鍵字，通過比較兩個根節(jié)點的關(guān)鍵字大小，其中較小的成為最小關(guān)鍵字，并成為新的根節(jié)點。另外一棵樹成為合并后的樹的一顆子樹。這個操作對于合并兩個二項堆而言是基礎(chǔ)的。</p><p>　　function mergeTree(p, q)</p><p>　　if p.root.key <= q.

50、root.key</p><p>　　return p.addSubTree(q)</p><p><b>　　else</b></p><p>　　return q.addSubTree(p)</p><p>　　對應(yīng)上圖，為了合并兩棵階數(shù)相同的二項樹，首先比較根節(jié)點的關(guān)鍵字。因為7> 3，在左邊的黑色樹（根節(jié)點

51、7）連接到灰樹（與根結(jié)點3）右邊的子樹。結(jié)果是棵3階樹。</p><p>　　合并兩個堆的操作也許是最有趣的，可以用來作為在大多數(shù)其他操作的子程序。和合并算法相似的是兩個二項堆的根節(jié)點鏈表同時被遍歷。</p><p>　　如果只有一個堆包含j階的樹，這棵樹被移動到合并后的堆。如果兩個堆都包含j階的樹，兩棵樹被合并成一顆滿足最小堆性質(zhì)的階數(shù)為j+1的二叉樹。注意這棵樹以后也可能要和某個堆中j

52、+1階的二叉樹合并。在算法的過程中，我們需要研究最三棵樹的任何順序的情況。</p><p>　　因為二項堆中的每棵二項樹與表示二項堆大小的二進制表示中的一位對應(yīng)，合并兩個二項堆與兩個二進制數(shù)相加是相似的。由右至左，每當一個進位產(chǎn)生時都意味著兩棵二項樹的合并。</p><p>　　每棵樹的階數(shù)不超過logn，因此運行時間是O（log n）的。</p><p>　　fu

53、nction merge(p, q)</p><p>　　while not( p.end() and q.end() )</p><p>　　tree = mergeTree(p.currentTree(), q.currentTree())</p><p>　　if not heap.currentTree().empty()</p><p&

54、gt;　　tree = mergeTree(tree, heap.currentTree())</p><p>　　heap.addTree(tree)</p><p><b>　　else</b></p><p>　　heap.addTree(tree)</p><p>　　heap.next() p.next() q

55、.next()</p><p>　　上圖表明合并兩個二項堆的過程。這是連續(xù)的合并階數(shù)相同的二叉樹來實現(xiàn)的。如果合并后的二叉樹又和兩個二項堆中某棵二叉樹階數(shù)相同，那么這兩棵二叉樹再次被合并。</p><p><b>　　插入</b></p><p>　　可以通過簡單地創(chuàng)建一個只包含此元素的新堆，然后將它與原來的堆合并。由于合并，插入需要O（log

56、 n）的時間，但它有一個攤銷時間為O（1）。</p><p><b>　　查找最小節(jié)點</b></p><p>　　查找堆的最小節(jié)點可以通過查找最小二項樹的根部。這可以再次輕松完成在O（log n）的時間，因為有只有O（log n）的二叉樹，因此要檢查的根節(jié)點不超過O(log n)。</p><p>　　通過使用指向最小節(jié)點的指針，此操作的時間

57、可以降低到O（1）。在執(zhí)行Find操作以外的任何操作必須更新指針的值。這些操作的時間復(fù)雜度依然是O(log n)。</p><p><b>　　刪除最小節(jié)點</b></p><p>　　要刪除堆的最小元素，首先找到這個元素然后從二叉樹中刪除它，獲得它的子樹的列表。通過將子樹按照階數(shù)從小到大重新排列形成一個新堆。然后合并這堆與原來的堆。由于每棵樹至多有 log n個孩子

58、，創(chuàng)建這個新堆的時間復(fù)雜度是O（log n）。合并堆的時間復(fù)雜度是O(log n)，所以整個刪除最小節(jié)點操作的時間復(fù)雜度是O(log n)。</p><p>　　function deleteMin(heap)</p><p>　　min = heap.trees().first()</p><p>　　for each current in heap.trees(

59、)</p><p>　　if current.root < min then min = current</p><p>　　for each tree in min.subTrees()</p><p>　　tmp.addTree(tree)</p><p>　　heap.removeTree(min)</p><

60、p>　　merge(heap, tmp)</p><p><b>　　減小節(jié)點值</b></p><p>　　減小某個節(jié)點關(guān)鍵字之后，它可能會比其父節(jié)點的關(guān)鍵字來的小，從而違背了最小堆的性質(zhì)。如果這種情況發(fā)生，交換其與父節(jié)點的關(guān)鍵字，也可能交互其與祖父節(jié)點的關(guān)鍵字，重復(fù)這個操作直到最小堆的性質(zhì)不再被違背。每棵二叉樹高度至多為log n，所以這需要O(log n)

61、的時間。</p><p><b>　　刪除</b></p><p>　　要從堆中刪除一個元素，減少其值至負無窮大（即低于堆中任意節(jié)點的關(guān)鍵字），然后刪除堆中的最小節(jié)點。</p><p><b>　　性能</b></p><p>　　對于有n個節(jié)點的二項堆，以下操作的時間復(fù)雜度為O(log n)：&l