Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Merging Binomial Queues

Merging two binomial queues is like doing binary addition. For example, consider the addition of tex2html_wrap_inline65760 and tex2html_wrap_inline65786:

tex2html_wrap_inline65474 tex2html_wrap_inline65610 tex2html_wrap_inline62528 tex2html_wrap_inline65468 tex2html_wrap_inline65466 tex2html_wrap_inline65760
+ tex2html_wrap_inline65610 tex2html_wrap_inline62528 tex2html_wrap_inline65468 tex2html_wrap_inline62528 tex2html_wrap_inline65786

tex2html_wrap_inline65788 tex2html_wrap_inline62528 tex2html_wrap_inline62528 tex2html_wrap_inline65794 tex2html_wrap_inline62528 tex2html_wrap_inline65466 tex2html_wrap_inline65800

The usual algorithm for addition begins with the least-significant ``bit.'' Since tex2html_wrap_inline65760 contains a tex2html_wrap_inline65466 tree and tex2html_wrap_inline65786 does not, the result is simply the tex2html_wrap_inline65466 tree from tex2html_wrap_inline65760.

In the next step, we add the tex2html_wrap_inline65468 from tex2html_wrap_inline65760 and the tex2html_wrap_inline65468 from tex2html_wrap_inline65786. Combining the two tex2html_wrap_inline65468s we get a tex2html_wrap_inline65794 which we carry  to the next column. Since there are no tex2html_wrap_inline65468s left, the result does not contain any. The addition continues in a similar manner until all the columns have been added up.

Program gif gives an implementation of this addition algorithm. The merge method of the BinomialQueue class takes a BinomialQueue and adds its subtrees to this binomial queue.

   program26737
Program: BinomialQueue class merge method.

Each iteration of the main loop of the algorithm (lines 16-42) computes the tex2html_wrap_inline57340 ``bit'' of the result--the tex2html_wrap_inline57340 bit is a binomial tree of order i. At most three terms need to be considered: the carry from the preceding iteration and two tex2html_wrap_inline65708s, one from each of the queues that are being merged.

Two methods, sum and carry, compute the result required in each iteration. Program gif defines both sum and carry. Notice that the sum method simply selects and returns one of its arguments. Therefore, the running time for sum is clearly O(1).

   program26755
Program: BinomialQueue class sum and carry methods.

In the worst case, the carry method calls the add method to combine two BinomialTrees into one. Therefore, the worst-case running time for carry is

displaymath65830

Suppose the merge method of Program gif is used to combine a binomial queue with n items with another that contains m items. Since the resulting priority queue contains n+m items, there are at most tex2html_wrap_inline65916 binomial trees in the result. Thus, the worst-case running time for the merge operation is

displaymath65831


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.