Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- (* 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")|] *)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement