the merge is performed by essentially adding the two queues together let be the new binomial queue since has no binomial tree of height and doeswe can just use the binomial tree of height in as part of nextwe add binomial trees of height since both and have binomial trees of height we merge them by making the larger root subtree of the smallercreating binomial tree of height shown in figure thush will not have binomial tree of height there are now three binomial trees of height namelythe original trees of and plus the tree formed by the previous step we keep one binomial tree of height in and merge the other twocreating binomial tree of height since and have no trees of height this tree becomes part of and we are finished the resulting binomial queue is shown in figure since merging two binomial trees takes constant time with almost any reasonable implementationand there are (log nbinomial treesthe merge takes (log ntime in the worst case to make this operation efficientwe need to keep the trees in the binomial queue sorted by heightwhich is certainly simple thing to do insertion is just special case of mergingsince we merely create one-node tree and perform merge the worst-case time of this operation is likewise (log nmore preciselyif 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 for exampleh (fig is missing binomial tree of height so the insertion will terminate in two steps since each tree in binomial queue is present with probability it follows that we expect an insertion to terminate in two stepsso the average time is constant furthermorean analysis will show that performing inserts on an initially empty binomial queue will take (nworst-case time indeedit is possible to do this operation using only comparisonswe leave this as an exercise as an examplewe show in figures through the binomial queues that are formed by inserting through in order inserting shows off bad case we merge figure merge of the two trees in and figure binomial queue the result of merging and