question 2

 (* Question 2 *)

  (* case where it doesnt work when recursion is removed *)
  (* The recursion is used when there are 2 swaps needing to be done, at different heights of the tree. This is because at each recursive call we are traversing through the height of the tree. In the example provided below, 13 and 11 need to swap at height 0, and 11 and 8 need to swap at height 1. *)

  let test = [|10;8;9;11;7;13|];;





  (* the second part, thanks Linda!! *)

let max_heapify_while_loop heap_size arr i =
  let len = Array.length arr in
  assert (heap_size <= len);
  let iRef = ref i in
  (* while the pointer iRef has not yet reached the leaves *)
  while (!iRef < (heap_size-1)/2+1) do
    let ai = arr.(!iRef) in
    let largest = ref (!iRef, arr.(!iRef)) in
    let l = left arr !iRef in
    let r = right arr !iRef in

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

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

    if !largest <> (!iRef, ai)
    then (swap arr !iRef (fst !largest);
          (* move pointer down along the path *)
          iRef := fst !largest)

  done;;

    (* Loop variant: when iRef = len-1  *)