Merge

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:^[1][3]

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

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 ${\displaystyle j}$, this tree is moved to the output heap. When both of the two heaps contain a tree of order ${\displaystyle j}$, the two trees are merged to one tree of order ${\displaystyle j+1}$ so that the minimum-heap property is satisfied. It may later become necessary to merge this tree with some other tree of order ${\displaystyle j+1}$ 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.^[1][3]

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.^[1][3]

Each binomial tree's traversal during merge only involves roots, hence making the time taken at most order ${\displaystyle \log _{2}n}$ and therefore the running time is ${\displaystyle O(\log n)}$.^[1][3]

Insert

Inserting a new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Because of the merge, a single insertion takes time ${\displaystyle O(\log n)}$. However, this can be sped up using a merge procedure that shortcuts the merge after it reaches a point where only one of the merged heaps has trees of larger order. With this speedup, across a series of ${\displaystyle k}$ consecutive insertions, the total time for the insertions is ${\displaystyle O(k+\log n)}$. Another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive insert has an amortized time of ${\displaystyle O(1)}$ (i.e. constant) per insertion.^[1][3]

A variant of the binomial heap, the skew binomial heap, achieves constant worst case insertion time by using forests whose tree sizes are based on the skew binary number system rather than on the binary number system.^[4]

Find minimum

To find the minimum element of the heap, find the minimum among the roots of the binomial trees. This can be done in ${\displaystyle O(\log n)}$ time, as there are just ${\displaystyle O(\log n)}$ tree roots to examine.^[1]

By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to ${\displaystyle O(1)}$. The pointer must be updated when performing any operation other than finding the minimum. This can be done in ${\displaystyle O(\log n)}$ time per update, without raising the overall asymptotic running time of any operation.

Delete minimum

To delete the minimum element from the heap, first find this element, remove it from the root of its binomial tree, and obtain a list of its child subtrees (which are each themselves binomial trees, of distinct orders). Transform this list of subtrees into a separate binomial heap by reordering them from smallest to largest order. Then merge this heap with the original heap. Since each root has at most ${\displaystyle \log _{2}n}$ children, creating this new heap takes time ${\displaystyle O(\log n)}$. Merging heaps takes time ${\displaystyle O(\log n)}$, so the entire delete minimum operation takes time ${\displaystyle O(\log n)}$.^[1]

function deleteMin(heap)
    min = heap.trees().first()
    for each current in heap.trees()
        if current.root < min.root then min = current
    for each tree in min.subTrees()
        tmp.addTree(tree)
    heap.removeTree(min)
    merge(heap, tmp)

Decrease key

After decreasing the key of an element, it may become smaller than the key of its parent, violating the minimum-heap property. If this is the case, exchange the element with its parent, and possibly also with its grandparent, and so on, until the minimum-heap property is no longer violated. Each binomial tree has height at most ${\displaystyle \log _{2}n}$, so this takes ${\displaystyle O(\log n)}$ time.^[1] However, this operation requires that the representation of the tree include pointers from each node to its parent in the tree, somewhat complicating the implementation of other operations.^[3]

Delete

To delete an element from the heap, decrease its key to negative infinity (or equivalently, to some value lower than any element in the heap) and then delete the minimum in the heap.^[1]