5.5. Maintaining Binary Heaps

• File: Heaps.ml (continued)

Let us now fix the broken heap bad_heap by restoring an order in it. As we can see, the issue there is between the parent (10, "c") and a left child (11, "f") that are out of order.

5.5.1. “Heapifying” elements of an array

What we need to do is to swap the offending parent with the children (assuming that both subtrees reachable from the children obey the descending order), and also make sure that the swapped element (10, "c") “sinks down”, finding its correct position in a reachable subtree. This procedure of “sinking” is what is implemented by the most important heap-manipulating function shown below:

(* 3. Restoring the heap property for an element i *)
let rec max_heapify heap_size arr i =
  let len = Array.length arr in
  assert (heap_size <= Array.length arr);
  if i > (len - 1) / 2 || i >= heap_size then ()
  else
    let ai = arr.(i) in
    let largest = ref (i, arr.(i)) in
    let l = left arr i in

    (* Shall we swap with the left child?.. *)
    if l <> None &&
       (fst (get_exn l)) < heap_size &&
       comp (snd (get_exn l)) (snd !largest) > 0
    then largest := get_exn l;

    (* May be the right child is even bigger? *)
    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)
    (* Okay, there is a necessity to progress further... *)
    then begin
      swap arr i (fst !largest);
      max_heapify heap_size arr (fst !largest)
    end

The implementation of max_heapify deserves some attention, as it is not entirely trivial. It takes three arguments, an integer heap_size (whose role will be explained shortly), and array arr representing the heap, and an index i of a parent element of an offending triple.

The heap_size serves the purpose of “limiting the scope” of a heap in an array and is always assumed to be less or equal than the array size. The reason why one might need it is because in some applications (as we will soon see), it is convenient to consider only a certain prefix of an array as a heap (and, thus obeying the heap definition), while the remaining suffix does not to be a part of it. One can, therefore, think of heap_size as of a “separator” between the heap-y and a non-heapy parts of an array.

The body of max_heapify is rather straightforward. It first assumes that the element at the position arr.(i) is the largest one. It then tries to retrieve its both children (if those are within the array size and heap size ranges), and determine the largest of them. If such one is present, it becomes the new parent, swapping with previous one. However, such a swap might have broken the heap-property in one of the subtrees, so the procedure needs to be repeated. Hence, the operation happens recursively for the new child (which used to be a parent, and now, after the swap, resides at the position !larger).

Question: Why does max_heapify terminate?

Let us now restore the heap using the max_heapify procedure:

let bad_heap =
   [|(16, "a"); (14, "b"); (9, "c"); (8, "d"); (7, "e"); (11, "f"); (3, "g");
   (2, "h"); (4, "i"); (1, "j"); (1, "k"); (10, "l"); (6, "m")|];;

# open KVHeaps;;
# is_heap bad_heap;;
- : bool = false

# is_heap_print ~print:true bad_heap;;
Out-of-order elements:
Parent: (2, (9, c))
Left: (5, (11, f))
Right: (6, (3, g))
- : bool = false

# max_heapify 13 bad_heap 2;;
- : unit = ()

# is_heap_print ~print:true bad_heap;;
- : bool = true

# bad_heap;;
- : (int * string) array =
[|(16, "a"); (14, "b"); (11, "f"); (8, "d"); (7, "e"); (10, "l"); (3, "g");
  (2, "h"); (4, "i"); (1, "j"); (1, "k"); (9, "c"); (6, "m")|]

As we can observe the two elements have now been correctly swapped.

5.5.2. Complexity of heapify

The maximal number of steps required to reach a child in a tree is called a height of a tree. Notice that the way max_heapify “walks” and array is by taking left/right child of an element. This way, it will make at most \(\log_2 n\) steps (which is the height of a heap). That is, the max_heapify procedure will terminate very quickly.

5.5.3. Building a heap from an array

We can now use max_heapify iteratively to turn an arbitrary array into a max-heap. The following code should be added to the Heap functor:

let build_max_heap arr =
  let len = Array.length arr in
  for i = (len - 1) / 2 downto 0 do
    max_heapify len arr i
  done

Question: Why does the for-loop start only from i = (len - 1) / 2, not from len - 1?

The complexity of build_max_heap can be over-approximated by analysing the complexity of each iteration of the while-loop, and the number of the iteration it makes.

Why does this procedure deliver a heap? This can be established by the following invariant, which we state in plain English (implementing it is a home exercise):

Invariant

At the start of each iteration of the for-loop in build_max_heap, each node i + 1, i + 2, len - 1 is a root of a max-heap.

Question: Why does this invariant holds for the elements from the second half of the array?

Question: What happens if we start building the heap from the beginning of the array, moving right. How correctness and performance will be affected? Justify your answer by talking about loop invariants.

We can test our procedure on some random arrays:

# let a = generate_key_value_array 10;;
val a : (int * string) array =
  [|(6, "ktesl"); (9, "herli"); (7, "etqiz"); (4, "wrnqu"); (3, "ceojd");
    (2, "cklpw"); (2, "mvcme"); (7, "uowmp"); (5, "yeuzq"); (4, "yuzdw")|]
# KVHeaps.build_max_heap a;;
- : unit = ()
# a;;
- : (int * string) array =
[|(9, "herli"); (7, "uowmp"); (7, "etqiz"); (6, "ktesl"); (4, "yuzdw");
  (2, "cklpw"); (2, "mvcme"); (4, "wrnqu"); (5, "yeuzq"); (3, "ceojd")|]
# is_heap a;;
- : bool = true