Merging Binomial Queues

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Merging Binomial Queues

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

The usual algorithm for addition begins with the least-significant ``bit.'' Since

contains a

tree and

does not, the result is simply the

tree from

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

Program 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.

program26946
Program: BinomialQueue class Merge method.

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

Two methods, Sum and Carry, compute the result required in each iteration. Program 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).

program26964
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

Suppose the Merge method of Program 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 binomial trees in the result. Thus, the worst-case running time for the Merge operation is