Я реализуюbinary heap используя список в OCaml, просто чтобы отточить свои навыки в OCaml.

Мне очень трудно пользоваться списком, и после двух дней борьбы я должен прийти сюда за предложениями и подсказками.

Вот моя мысль пока

Очевидно, я могут использовать оригиналarray based алгоритм его реализации с использованием списка.

То, что я пытаюсь использовать, этоbinary tree, Я должен держатьinvariant что узел должен быть больше любого узла, уровень которого ниже его.

Я примерно разобрался как реализоватьinsertХотя я не уверен, правильно ли это или нет.

Для двоичного дерева каждый узел имеетtwo childrenvalue а такжеsize n что общее количествоoffsprings она имеет, этоn используется для балансировки дерева.

При вставкеxЯ сравниваю с узлом (от корня, рекурсивно). Предполагатьx < the value of the node, затем

Если один или оба узла "с детьмиLeafзатем я вставляюx в это место листьев.

Еслиnone узла "s дети Leaf, тогда я выберу ребенка, чье n меньше, а затем.recursively insert

Вот мой код

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