Binomial heaps: proof that merging is done in O (log n) time

Question

I am reading Okasaki Purely Functional Data Structures and trying to do some exercises. One of them is to prove that the binomial heap merge takes O(log n) time, when n is the number of nodes in the heap.

 functor BinomialHeap (Element:ORDERED):HEAP= struct structure Elem=Element datatype Tree = Node of int*Elem.T*Tree list type Heap = Tree list fun link (t1 as Node (r,x1,c1), t2 as Node (_,x2,c2))= if Elem.leq(x1,x2) then Node (r+1,x1,t2::c1) else Node (r+1,x2,t1::c2) fun insTree (t,[])=[t] |insTree (t,ts as t'::ts')= if rank t < rank t' then t::ts else insTree(link(t,t'),ts') fun insert (x,ts)=insTree(Node(0,x,[]),ts) (*just for reference*) fun merge (ts1,[])=ts1 |merge ([],ts2)=ts2 |merge (ts1 as t1::ts1', ts2 as t2:ts2')= if rank t1 < rank t2 then t1::merge(ts1',ts2) else if rank t2 < rank t1 then t2::merge(ts1,ts2') else insTree (link(t1,t2), merge (ts1',ts2')) end 

It's clear that merge will call itself max(numNodes ts1, numNodes ts2) times, but since insTree less than O(log n) , can you explain how merge is O(log n) ?

Answer 1

First, note that merge will be called no more than (numNodes ts1 + numNodes ts2) times, and this is O(log n) times. (To be clear, ts1 and ts2 are lists of binomial trees where such a tree of rank r contains exactly 2^r nodes, and each rank can occur no more than once. Therefore, there are O(log n1) such trees in ts1 and O(log n2) in ts2 , where n1 and n2 are the number of nodes in heaps and n=n1+n2 .)

The key point is that insTree is called no more than once for each rank (either through merge or recursively), and the largest possible rank is log_2(n) . The reason is as follows:

If insTree is called from merge , say r = rank t1 = rank t2 , and link(t1,t2) will be rank r+1 . So let insTree called for rank r+1 . Now think about what happens to merge(ts1', ts2') . Let the smallest rank that occurs as a tree in ts1' and ts2' be r' >= r+1 . Then insTree will again be called from merge for rank r'+1 , since two trees of rank r' will be associated with the formation of a tree of rank r'+1 . However, the merge heap merge(ts1', ts2') therefore cannot contain the rank tree r' , and the previous call to insTree may therefore not return further than r' .

So, let's connect things:

• insTree is called no more than O(log n) times, and each call is constant (since we count recursion as a separate call)

• merge is called no more than O(log n) times, and each call is constant (since we count insTree calls separately, and link is a constant time)

=> The whole merge operation is O(log n) .

EDIT: By the way, merging binomial heaps is very similar to adding binary numbers. A heap of size n will have a tree of rank r if and only if the binary number n has "1" at position 2^r . When merging such heaps, you go from the lowest rank to the highest rank - or the least significant for the most significant position. Trees of the same rank should be connected ("one" added) and inserted / "moved" to positions of a higher rank.