I am reading Binomial Heap
in Purely Functional Data Structures.
The implementation of insTree
function confused me quite much. Here are the set of codes
datatype Tree = Node of int * Elem.T * 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 rank (Node (r, x, c)) = r
fun insTree (t, []) = [t]
| insTree (t, ts as t' :: ts') =
if rank t < rank t' then t::ts else insTree (link (t, t'), ts')
My confusion lies on the bit in insTree
that why it does not consider the situation of rank t > rank t'?
In if rank t < rank t' then t::ts else insTree (link (t, t'), ts')
,
I thought the process of inserting a binomial tree into a binomial heap
should be like this:
rank+1
new tree and try again insert the new tree to the heap.So, I think the correct fun insTree
could be like this:
fun insTree (t, []) = [t]
| insTree (t, ts as t' :: ts') =
if rank t < rank t' then t::ts
else if rank t = rank t' then insTree (link (t, t'), ts')
else t'::(insTree (t, ts'))
insTree is a helper function that is not visible to the user. The user calls insert, which in turn calls insTree with a tree of rank 0, and a list of trees of increasing rank. insTree has an invariant that the rank of t is <= the rank of the first tree in the list. So if it's not <, then it must be =.
You're right that if insTree was a general-purpose public function, rather than a special-purpose private function, then it would have to deal with the missing case.