Estou implementando umbinary heap usando lista no OCaml, apenas para aguçar minhas habilidades no OCaml.

Eu sinto muito difícil usar lista e depois de lutar por dois dias, eu tenho que vir aqui para sugestões e sugestões.

Aqui está o meu pensamento até agora

Obviamente, não posso usar o orignalarray based algoritmo para implementá-lo usando a lista.

O que estou tentando usar ébinary tree. Eu tenho mantido oinvariant que um nó deve ser maior que qualquer nó cujo nível seja menor que o seu.

Eu aproximadamente descobri como implementarinsert, embora eu não tenha certeza se está correto ou não.

Para a árvore binária, cada nó temtwo children, value esize n que é o número total deoffsprings tem. esten é usado para equilibrar a árvore.

Ao inserirx, Eu comparo com um nó (da raiz, recursivamente). Assumirx < the value of the node, então

Se um ou ambos os filhos do nóLeaf, então eu insiro ox para aquele lugar da Folha.

E senone dos filhos do nó são Leaf, então eu vou escolher a criança cujo n é menor e, em seguida,recursively insert.

Aqui está meu código

type 'a heap = 
  | Node of 'a * 'a heap * 'a heap * int
  | Leaf 

exception EmptyHeapException

let create_heap () = Leaf;;

let rec insert x = function
  | Leaf -> Node (x, Leaf, Leaf, 0)
  | Node (v, l, r, n) ->
    let (stay, move) = if x > v then (x, v) else (v, x)
    in 
    match (l, r) with 
      | (Leaf, Leaf) -> 
        Node (stay, Node (move, Leaf, Leaf, 0), Leaf, 1)
      | (Leaf, _) -> 
        Node (stay, Node (move, Leaf, Leaf, 0), r, n+1)
      | (_, Leaf) ->
        Node (stay, l, Node (move, Leaf, Leaf, 0), n+1)
      | (Node (_, _, _, n1), Node (_, _, _, n2)) ->
        if n1 <= n2 then
          Node (stay, (insert move l), r, n1+1)
        else 
          Node (stay, l, (insert move r), n2+1);;

Ok, eu tenho as seguintes perguntas.

Estou indo para a direção correta? Meu pensamento ou implementação está correto?Eu fico preso na implementaçãoget_top função. Eu não sei como continuar. Alguma dica?baterias ocaml implementaram uma eficientebatHeap.ml. Eu dei uma olhada, mas sinto que o caminho é totalmente diferente do meu e não consigo entender. Qualquer um pode me ajudar a entender isso?