• API
• FAQ
• Tools
• Archive
SHARE
TWEET

question 2

a guest Feb 17th, 2019 52 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1.  (* Question 2 *)
2.
3.   (* case where it doesnt work when recursion is removed *)
4.   (* 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. *)
5.
6.   let test = [|10;8;9;11;7;13|];;
7.
8.
9.
10.
11.
12.   (* the second part, thanks Linda!! *)
13.
14. let max_heapify_while_loop heap_size arr i =
15.   let len = Array.length arr in
16.   assert (heap_size <= len);
17.   let iRef = ref i in
18.   (* while the pointer iRef has not yet reached the leaves *)
19.   while (!iRef < (heap_size-1)/2+1) do
20.     let ai = arr.(!iRef) in
21.     let largest = ref (!iRef, arr.(!iRef)) in
22.     let l = left arr !iRef in
23.     let r = right arr !iRef in
24.
25.     if l <> None &&
26.          (fst (get_exn l) < heap_size) &&
27.            (comp (snd (get_exn l)) (snd !largest) > 0)
28.     then largest := get_exn l;
29.
30.     if r <> None &&
31.          (fst (get_exn r) < heap_size) &&
32.            (comp (snd (get_exn r)) (snd !largest) > 0)
33.     then largest := get_exn r;
34.
35.     if !largest <> (!iRef, ai)
36.     then (swap arr !iRef (fst !largest);
37.           (* move pointer down along the path *)
38.           iRef := fst !largest)
39.
40.   done;;
41.
42.     (* Loop variant: when iRef = len-1  *)
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