- To merge two binomial queues, an operation similar to addition of
binary integers is performed:
- At any stage, we may have zero, one, two, or three
*B*_{k}trees, depending on whether or not the two priority queues contain a*B*_{k}tree and whether or not a*B*_{k}tree is carried over from the previous step.- if there is zero or more
*B*_{k}tree, it is placed as a tree in the resulting binomial queue. - If there are two, they are merged into a
*B*_{k + 1}tree and carried over - If there are three, one is retained and other two merged.

- if there is zero or more

**Result 1:**

- A binomial queue of
*n*elements can be built by*n*successive insertions in 0(*n*) time. - Brute force Analysis

Define the cost of each insertions to be- 1time unit + an extra unit for each linking step

Thus the total will be*n*units plus the total number of linking steps. - The 1st, 3rd, ... and each odd-numbered step requires no linking steps since there is no
*B*_{0}present. - A quarter of the insertions require only one linking step: 2nd, 6th, 10, ...
- One eighth of insertions require two linking steps.

We could do all this and bound the number of linking steps by

*n*.The above analysis will not help when we try to analyze a sequence of operations that include more than just insertions.

- 1time unit + an extra unit for each linking step
- Amortized Analysis
Consider the result of an insertion.

- If there is no
*B*_{0}tree, then the insertion costs one time unit. The result of insertion is that there is now a*B*_{0}tree and the forest has one more tree. - If there is a
*B*_{0}tree but not*B*_{1}tree, then insertion costs 2 time units. The new forest will have a*B*_{1}tree but not a*B*_{0}tree. Thus number of trees in the forest is unchanged. - An insertion that costs 3 time units will create a
*B*_{2}tree but destroy a*B*_{0}and*B*_{1}, yielding one less tree in the forest. - In general, an insertion that costs
*c*units results in a net increase of 2 -*c*trees. Since- a
*B*_{c - 1}tree is created - all
*B*_{i}trees, 0*i**c*- 1 are removed.

*Let**t*_{i}=*c*_{i}=We have

*c*_{0}=0 *t*_{i}+ (*c*_{i}-*c*_{i - 1}) =2 - a

- If there is no

**Result 2:**

- The amortized running times of Insert, Delete-min, and Merge are
0(1), 0(log
*n*), and 0(log*n*) respectively.- Potential function = # of trees in the queue

- Insertion
*t*_{i}= *c*_{i}= *a*_{i}= *t*_{i}+ (*c*_{i}-*c*_{i - 1})*a*_{i}= 2 *i**t*_{i}= *a*_{i}- (*c*_{n}-*c*_{0})= 2 *n*- (*c*_{n}-*c*_{0})As long as (

*c*_{n}-*c*_{0}) is positive, we are done.In any case (

*c*_{n}-*c*_{0}) is bounded by log*n*if we start with an empty tree. - Merge:
Assume that the two queues to be merged have

*n*_{1}and*n*_{2}nodes with*T*_{1}and*T*_{2}trees. Let*n*=*n*_{1}+*n*_{2}. Actual time to perform merge is given by:*t*_{i}= 0(log *n*_{1}+ log*n*_{2})= 0( *max*(log*n*_{1}, log*n*_{2})= 0(log *n*)*c*_{i}-*c*_{i - 1}) is at most (log*n*) since there can be at most (log*n*) trees after merge. - Deletemin:

The analysis here follows the same argument as for merge.