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

Putting Items into a Binomial Queue

With the merge method at our disposal, the enqueue operation is easy to implement. To enqueue an item in a given binomial queue, we create another binomial queue that contains just the one item to be enqueued and merge that queue with the original one.

Program gif shows how easily this can be done. Creating the empty queue (line 9) takes a constant amount of time. Creating the binomial tree tex2html_wrap_inline65466 with the one object at its root (line 10) can also be done in constant time. Finally, the time required to merge the two queues is

displaymath65918

where n is the number of items originally in the queue.

   program26781
Program: BinomialQueue class enqueue method.


next up previous contents index

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