Exercise 2.1

(* remove a self-recursive call from the end of max_heapify *)
let rec max_heapify_removed heap_size arr i =
  let len = Array.length arr in
  assert (heap_size <= Array.length arr);
  if i > (len - 1) / 2 then ()
  else
    let ai = arr.(i) in
    let largest = ref (i, arr.(i)) in
    let l = left arr i in

    if l <> None &&
       (fst (get_exn l)) < heap_size &&
       comp (snd (get_exn l)) (snd !largest) > 0
    then largest := get_exn l;

    let r = right arr i in
    if r <> None &&
       (fst (get_exn r)) < heap_size &&
       comp (snd (get_exn r)) (snd !largest) > 0
    then largest := get_exn r;

    if !largest <> (i, ai)
    then
       swap arr i (fst !largest);;
        (* max_heapify heap_size arr (fst !largest));; *)

let arr = [|(16, "a"); (3, "g"); (14, "b"); (11, "f"); (10, "c"); (8, "d"); (7, "e"); (2, "h"); (4, "i"); (1, "j")|];;
max_heapify_removed 10 arr 1;;
arr;;
(* - : KVHeaps.t array =
[|(16, "a"); (11, "f"); (14, "b"); (3, "g"); (10, "c"); (8, "d"); (7, "e");
  (2, "h"); (4, "i"); (1, "j")|] *)