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.
Merge
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.
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 , if we define the random variable X as representing the number of steps in an insert operation, then
X | = 1 | |
= 2 | ||
= 3 | ||
*15pt |
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.
Deletemin
Implementation of a Binomial Queue
data | first | left | right | rank No. of |
child | sibling | sibling | children |