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

Binomial Queues

If binomial trees only come in sizes that are powers of two, how do we implement a container which holds an arbitrary number number of items n using binomial trees? The answer is related to the binary representation of the number n. Every non-negative integer n can be expressed in binary form as

  equation26541

where tex2html_wrap_inline65977 is the tex2html_wrap_inline57621 binary digit   or bit  in the representation of n. For example, n=27 is expressed as the binary number tex2html_wrap_inline65985 because 27=16+8+2+1.

To make a container which holds exactly n items we use a collection of binomial trees. A collection of trees is called a forest . The forest contains binomial tree tex2html_wrap_inline65991 if the tex2html_wrap_inline57621 bit in the binary representation of n is a one. That is, the forest tex2html_wrap_inline59641 which contains exactly n items is given by

displaymath65969

where tex2html_wrap_inline66001 is determined from Equation gif. For example, the forest which contains 27 items is tex2html_wrap_inline66003

The analogy between tex2html_wrap_inline59641 and the binary representation of n carries over to the merge operation. Suppose we have two forests, say tex2html_wrap_inline59641 and tex2html_wrap_inline66011. Since tex2html_wrap_inline59641 contains n items and tex2html_wrap_inline66011 contains m items, the combination of the two contains n+m items. Therefore, the resulting forest is tex2html_wrap_inline66023.

For example, consider n=27 and m=10. In this case, we need to merge tex2html_wrap_inline66029 with tex2html_wrap_inline66031. Recall that two binomial trees of order k can be combined to obtain a binomial tree of order k+1. For example, tex2html_wrap_inline66037. But this is just like adding binary digits! In binary notation, the sum 27+10 is calculated like this:

11011
+ 1010

100101

The merging of tex2html_wrap_inline66043 and tex2html_wrap_inline66045 is done in the same way:

tex2html_wrap_inline65757 tex2html_wrap_inline65893 tex2html_wrap_inline62795 tex2html_wrap_inline65751 tex2html_wrap_inline65749 tex2html_wrap_inline66043
+ tex2html_wrap_inline65893 tex2html_wrap_inline62795 tex2html_wrap_inline65751 tex2html_wrap_inline62795 tex2html_wrap_inline66069

tex2html_wrap_inline66071 tex2html_wrap_inline62795 tex2html_wrap_inline62795 tex2html_wrap_inline66077 tex2html_wrap_inline62795 tex2html_wrap_inline65749 tex2html_wrap_inline66083

Therefore, the result is tex2html_wrap_inline66085.


next up previous contents index

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