计算机科学外文翻译(编辑修改稿)

计算机科学外文翻译(编辑修改稿)内容摘要：

ecause 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 righttoleft. 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) while not( () and () ) tree = mergeTree((), ()) if not ().empty() tree = mergeTree(tree, ()) (tree) else (tree) () () () This shows the merger of two binomial heaps. This is acplished 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 those two are merged again. Insert Inserting a 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, however it has an amortized time of O(1) (. constant). Find minimum To find the minimum element 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 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 raising the running time of any operation. Delete minimum To delete the minimum element 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 most 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 = ()。