• API
• FAQ
• Tools
• Archive
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.

Top