Editing Binomial heap (section)

=== Merge ===
[[File:Binomial heap merge1.svg|thumb|200px|To merge two binomial trees of the same order, first compare the root key. Since 7>3, the black tree on the left (with root node 7) is attached to the grey tree on the right (with root node 3) as a subtree. The result is a tree of order 3.]]

The operation of '''merging''' two heaps is used as a subroutine in most other operations.
A basic subroutine within this procedure merges pairs of binomial trees of the same order. This may be done by comparing the keys at the roots of the two trees (the smallest keys in both trees). The root node with the larger key is made into a child of the root node with the smaller key, increasing its order by one:<ref name="clrs" /><ref name="brown" />

 '''function''' mergeTree(p, q)
     '''if''' p.root.key <= q.root.key
         '''return''' p.addSubTree(q)
     '''else'''
         '''return''' q.addSubTree(p)

[[File:Binomial heap merge2.svg|thumb|300px|This shows the merger of two binomial heaps. This is accomplished by merging two binomial trees of the same order one by one. If the resulting merged tree has the same order as one binomial tree in one of the two heaps, then those two are merged again.]]

To merge two heaps more generally, the lists of roots of both heaps are traversed simultaneously in a manner similar to that of the [[merge algorithm]],
in a sequence from smaller orders of trees to larger orders. When only one of the two heaps being merged contains a tree of order <math>j</math>, this tree is moved to the output heap. When both of the two heaps contain a tree of order <math>j</math>, the two trees are merged to one tree of order <math>j+1</math> so that the minimum-heap property is satisfied. It may later become necessary to merge this tree with some other tree of order <math>j+1</math> in one of the two input heaps. In the course of the algorithm, it will examine at most three trees of any order, two from the two heaps we merge and one composed of two smaller trees.<ref name="clrs" /><ref name="brown" />

 '''function''' merge(p, q)
     '''while''' '''not''' (p.end() '''and''' q.end())
         tree = mergeTree(p.currentTree(), q.currentTree())

         '''if''' '''not''' heap.currentTree().empty()
             tree = mergeTree(tree, heap.currentTree())

         heap.addTree(tree)
         heap.next(); p.next(); q.next()

Because each binomial tree in a binomial heap corresponds to a bit in the binary representation of its size, there is an analogy between the merging of two heaps and the binary addition of the ''sizes'' of the two heaps, from right-to-left. Whenever a carry occurs during addition, this corresponds to a merging of two binomial trees during the merge.<ref name="clrs" /><ref name="brown" />

Each binomial tree's traversal during merge only involves roots, hence making the time taken at most order <math>\log_2 n</math> and therefore the running time is <math>O(\log n)</math>.<ref name="clrs" /><ref name="brown" />