計(jì)算機(jī)科學(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>　　二項(xiàng)堆</b></p><p>　　在計(jì)算機(jī)科學(xué)中，二項(xiàng)堆是一個(gè)二叉堆類似的堆結(jié)構(gòu)，但是支持兩個(gè)二項(xiàng)堆快速合并。這是通過使用一個(gè)特殊的樹結(jié)構(gòu)。實(shí)現(xiàn)可合并堆的抽象數(shù)據(jù)類型（也稱為meldable堆）是重要的，這個(gè)抽象數(shù)據(jù)結(jié)構(gòu)就是支持合并操

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

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

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

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

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

49、堆中合并兩個(gè)階數(shù)相同的二叉樹。由于二叉樹的結(jié)構(gòu)，它們能夠被輕易的合并。由于二叉樹的根節(jié)點(diǎn)具有最小關(guān)鍵字，通過比較兩個(gè)根節(jié)點(diǎn)的關(guān)鍵字大小，其中較小的成為最小關(guān)鍵字，并成為新的根節(jié)點(diǎn)。另外一棵樹成為合并后的樹的一顆子樹。這個(gè)操作對(duì)于合并兩個(gè)二項(xiàng)堆而言是基礎(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>　　對(duì)應(yīng)上圖，為了合并兩棵階數(shù)相同的二項(xiàng)樹，首先比較根節(jié)點(diǎn)的關(guān)鍵字。因?yàn)?> 3，在左邊的黑色樹（根節(jié)點(diǎn)

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

52、+1階的二叉樹合并。在算法的過程中，我們需要研究最三棵樹的任何順序的情況。</p><p>　　因?yàn)槎?xiàng)堆中的每棵二項(xiàng)樹與表示二項(xiàng)堆大小的二進(jìn)制表示中的一位對(duì)應(yīng)，合并兩個(gè)二項(xiàng)堆與兩個(gè)二進(jìn)制數(shù)相加是相似的。由右至左，每當(dāng)一個(gè)進(jìn)位產(chǎn)生時(shí)都意味著兩棵二項(xiàng)樹的合并。</p><p>　　每棵樹的階數(shù)不超過logn，因此運(yùn)行時(shí)間是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>　　上圖表明合并兩個(gè)二項(xiàng)堆的過程。這是連續(xù)的合并階數(shù)相同的二叉樹來實(shí)現(xiàn)的。如果合并后的二叉樹又和兩個(gè)二項(xiàng)堆中某棵二叉樹階數(shù)相同，那么這兩棵二叉樹再次被合并。</p><p><b>　　插入</b></p><p>　　可以通過簡(jiǎn)單地創(chuàng)建一個(gè)只包含此元素的新堆，然后將它與原來的堆合并。由于合并，插入需要O（log

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

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

58、，創(chuàng)建這個(gè)新堆的時(shí)間復(fù)雜度是O（log n）。合并堆的時(shí)間復(fù)雜度是O(log n)，所以整個(gè)刪除最小節(jié)點(diǎn)操作的時(shí)間復(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é)點(diǎn)值</b></p><p>　　減小某個(gè)節(jié)點(diǎn)關(guān)鍵字之后，它可能會(huì)比其父節(jié)點(diǎn)的關(guān)鍵字來的小，從而違背了最小堆的性質(zhì)。如果這種情況發(fā)生，交換其與父節(jié)點(diǎn)的關(guān)鍵字，也可能交互其與祖父節(jié)點(diǎn)的關(guān)鍵字，重復(fù)這個(gè)操作直到最小堆的性質(zhì)不再被違背。每棵二叉樹高度至多為log n，所以這需要O(log n)

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