Я определил кучу типов:
type 'a heap =
| Node of int * int * 'a heap * 'a heap
| Leaf;;
И следующие функции:
let rank = function Leaf -> 0 | Node (r,_,_,_) -> r;;
let makeNode x a b =
if rank a>= rank b then Node(rank b+1,x,a,b)
else Node (rank a+1,x,a,b);;
let rec meld = function
|h,Leaf | Leaf,h -> h
| (Node(f,x,a1,b1)as h1),(Node(g,y,a2,b2)as h2) -> if x >= y then makeNode x a1 (meld (b1, h2))
else makeNode y a2 (meld (h1, b2));;
let insert h x = meld ((Node(1,x,Leaf,Leaf)), h);;
Однако, когда я вставляю в кучу второй узел, корень исчезает. Как я могу это исправить:
let makeheap x = Node(1,x,Leaf,Leaf);;
let myheap = makeheap 5;;
insert myheap 7;;
insert myheap 8;;
insert myheap 3;;
приводит к следующему результату:
val myheap : 'a heap = Node(1,5,Leaf,Leaf)
'a heap = Node(1,7,Leaf,Node(1,5,Leaf,Leaf))
'a heap = Node (1,8,Leaf,Node(1,5,Leaf,Leaf))
'a heap = Node(1,5,Leaf,Node(1,3,Leaf,Leaf))