(**************************************************************************)
(*                                                                        *)
(*  Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre,       *)
(*  Kim Nguyen, Laurent Sartre                                            *)
(*                                                                        *)
(*  Informatique - MP2I/MPI - CPGE 1re et 2e années.                      *)
(*  Cours et exercices corrigés. Éditions Ellipses, 2022.                 *)
(*                                                                        *)
(*  https://www.informatique-mpi.fr/                                      *)
(*                                                                        *)
(**************************************************************************)

(* Files de priorité immuables, réalisées avec des skew heaps

   L'ordre utilisé ici est la comparaison structurelle polymorphe d'OCaml. *)

type 'a heap = E | N of 'a heap * 'a * 'a heap

let empty : 'a heap =
  E

let is_empty (t: 'a heap) : bool =
  t = E

let rec merge (t1: 'a heap) (t2: 'a heap) : 'a heap =
  match t1, t2 with
  | E, t | t, E ->
      t
  | N (l1, x1, r1), N (l2, x2, r2) ->
      if x1 <= x2 then
        N (merge r1 t2, x1, l1)
      else
        N (merge r2 t1, x2, l2)

let insert (x: 'a) (t: 'a heap) : 'a heap =
  merge (N (E, x, E)) t

let get_min (t: 'a heap) : 'a =
  match t with
  | E -> invalid_arg "get_min"
  | N (_, x, _) -> x

let extract_min (t: 'a heap) : 'a * 'a heap =
  match t with
  | E -> invalid_arg "extract_min"
  | N (l, x, r) -> x, merge l r

let rec height t = match t with
  | E -> -1
  | N (l, _, r) -> 1 + max (height l) (height r)