daily pastebin goal
29%
SHARE
TWEET

Exercise 2.1

a guest Feb 17th, 2019 71 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. (* remove a self-recursive call from the end of max_heapify *)
  2. let rec max_heapify_removed heap_size arr i =
  3.   let len = Array.length arr in
  4.   assert (heap_size <= Array.length arr);
  5.   if i > (len - 1) / 2 then ()
  6.   else
  7.     let ai = arr.(i) in
  8.     let largest = ref (i, arr.(i)) in
  9.     let l = left arr i in
  10.  
  11.     if l <> None &&
  12.        (fst (get_exn l)) < heap_size &&
  13.        comp (snd (get_exn l)) (snd !largest) > 0
  14.     then largest := get_exn l;
  15.  
  16.     let r = right arr i in
  17.     if r <> None &&
  18.        (fst (get_exn r)) < heap_size &&
  19.        comp (snd (get_exn r)) (snd !largest) > 0
  20.     then largest := get_exn r;
  21.  
  22.     if !largest <> (i, ai)
  23.     then
  24.        swap arr i (fst !largest);;
  25.         (* max_heapify heap_size arr (fst !largest));; *)
  26.  
  27. let arr = [|(16, "a"); (3, "g"); (14, "b"); (11, "f"); (10, "c"); (8, "d"); (7, "e"); (2, "h"); (4, "i"); (1, "j")|];;
  28. max_heapify_removed 10 arr 1;;
  29. arr;;
  30. (* - : KVHeaps.t array =
  31. [|(16, "a"); (11, "f"); (14, "b"); (3, "g"); (10, "c"); (8, "d"); (7, "e");
  32.   (2, "h"); (4, "i"); (1, "j")|] *)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top