Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
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_inline66888 and tex2html_wrap_inline66914:

tex2html_wrap_inline66602 tex2html_wrap_inline66738 tex2html_wrap_inline63650 tex2html_wrap_inline66596 tex2html_wrap_inline66594 tex2html_wrap_inline66888
+ tex2html_wrap_inline66738 tex2html_wrap_inline63650 tex2html_wrap_inline66596 tex2html_wrap_inline63650 tex2html_wrap_inline66914

tex2html_wrap_inline66916 tex2html_wrap_inline63650 tex2html_wrap_inline63650 tex2html_wrap_inline66922 tex2html_wrap_inline63650 tex2html_wrap_inline66594 tex2html_wrap_inline66928

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

In the next step, we add the tex2html_wrap_inline66596 from tex2html_wrap_inline66888 and the tex2html_wrap_inline66596 from tex2html_wrap_inline66914. Combining the two tex2html_wrap_inline66596s we get a tex2html_wrap_inline66922 which we carry  to the next column. Since there are no tex2html_wrap_inline66596s 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 member function of the BinomialQueue class takes a reference to a BinomialQueue and adds its subtrees to this binomial queue.

   program27585
Program: BinomialQueue Class Merge Member Function Definition

Each iteration of the main loop of the algorithm (lines 12-24) computes the tex2html_wrap_inline58387 ``bit'' of the result--the tex2html_wrap_inline58387 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_inline66836s, one from each of the queues that are being merged.

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

   program27603
Program: BinomialQueue Class Sum and Carry Member Function Definitions

In the worst case, the Carry function calls the Add function to combine two BinomialTrees into one. Therefore, the worst-case running time for Carry is

displaymath66932

Suppose the Merge routine 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_inline67046 binomial trees in the result. Thus, the running time for the Merge operation is

displaymath66961


next up previous contents index

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