datatype Tree = Node of int * Elem.T * Tree list
type Heap = Tree list
fun rank (Node (r,x,c)) = r
fun link (t1 as Node (r1, x1, c1), t2 as Node (r2, 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 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'))
Средний
Простой
Средний
