(********************************************************************)
(*  OCaml code from the book ``Learn Programming with OCaml''       *)
(*  See https://usr.lmf.cnrs.fr/lpo/                                *)
(*                                                                  *)
(*  Sylvain Conchon and Jean-Christophe Filliâtre                   *)
(*  Copyright 2025 Université Paris-Saclay and CNRS                 *)
(*                                                                  *)
(*  Openly licensed via CC BY SA 4.0                                *)
(*  See https://creativecommons.org/licenses/by-sa/4.0/deed.en      *)
(********************************************************************)

(* Program 63 on page 281
   An imperative heap data structure (1/2) *)

module type OrderedWithDummy = sig
  type t
  val compare: t -> t -> int
  val dummy: t
end

module Make(X: OrderedWithDummy)(A: ResizeableArray)
  : ImperativePriorityQueue with type elt = X.t =
struct
  type elt = X.t
  type t = elt A.t

  let create () =
    A.make 0 X.dummy

  let is_empty h =
    A.length h = 0

  let get_min h =
    if A.length h = 0 then invalid_arg "get_min";
    A.get h 0

  let rec move_up h x i =
    if i = 0 then A.set h i x else
      let fi = (i - 1) / 2 in
      let y = A.get h fi in
      if X.compare y x > 0 then begin
        A.set h i y;
        move_up h x fi
      end else
        A.set h i x

  let add x h =
    let n = A.length h in A.resize h (n + 1); move_up h x n

This document was generated using caml2html