Next:6.2.2 Binomial Amortized AnalysisUp:6.2 Binomial QueuesPrevious:6.2 Binomial Queues

6.2.1 Binomial Queue Operations


This is implemented by scanning the roots of all the trees. Since there are at most log n different trees, this leads to a worstcase complexity of 0(log n).

Alternatively, one can keep track of the current minimum and perform find-min in 0(1) time if we remember to update the minimum if it changes during other operations.


Let H1: 6 elements

H2: 7 elements

We are now left with

1 tree of height 0

3 trees of height 2

Note that of the 3 binomial trees of height 2, we could have any pair to get another binomial heap. Since merging two binomial trees takes constant time and there are 0(log n) binomial trees, merge takes 0(log n) in the worstcase. See Figures 6.7 and 6.8 for two examples. 

Figure 6.7: Examples of Merging

Figure 6.8: Merge of H1 and H2

This is a special case of merging since we merely create a one-node tree and perform a merge.

Worstcase complexity therefore will be O(log n).

More precisely; if the priority queue into which the element is being inserted has the property that the smallest nonexistent binomial tree is Bi, the running time is proportional to i + 1.

Eg: Insertion into H3 (which has 13 elements) terminates in two steps.

Since each tree of a particular degree in a binomial queue is present with probability $ {\frac{1}{2}}$, if we define the random variable X as representing the number of steps in an insert operation, then 

Figure 6.9: Examples of Inserts
X = 1 $\displaystyle \mbox{with prob $\frac{1}{2}$\space $(B_{0}$\spacenot present)}$
  = 2 $\displaystyle \mbox{with prob $\frac{1}{2}$\space $(B_{0}$\space not present)$(B_{1}$\space not present)}$
  = 3 $\displaystyle \mbox{with prob $\frac{1}{8}$ }$
   *15pt$ \vdots$  
Thus average number of steps in an insert operation = 2

Thus we expect an insertion to terminate in two steps on the average. Further more, performing n inserts on an initially empty binomial queue will take 0(n) worstcase time.

See Figures 6.9 and 6.10 for an example.


Figure 6.10: Merges of H' and H''
It is easy to see that the worstcase complexity of deletemin is 0(log n).

Implementation of a Binomial Queue

Next:6.2.2 Binomial Amortized AnalysisUp:6.2 Binomial QueuesPrevious:6.2 Binomial Queues