Data Structures and Algorithms with Object-Oriented Design Patterns in C#
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_inline65749 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

displaymath66201

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

   program26990
Program: BinomialQueue class Enqueue method.


next up previous contents index

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