# 5.8. Exercises¶

## 5.8.1. Exercise 1¶

1. What is a maximal and a minimal number of elements in a heap of the height $$h$$? Explain your answer and give examples.
2. Is an array that is sorted a min-heap?
3. Where in a max-heap might the elements with the smallest keys reside, assuming that all keys are distinct?

## 5.8.2. Exercise 2¶

• Let us remove a self-recursive call at the end of max_heapify. Give a concrete example of an array arr, which is almost a heap (with just one offending triple rooted at i), such that the procedure max_heapify (Array.length arr) arr i does not restore a heap, unless run recursively.
• Rewrite max_heapify so it would use a while-loop instead of the recursion. Provide a variant for this loop.

## 5.8.3. Exercise 3¶

Implement in OCaml and check an invariant from Section Building a heap from an array. Explain how it implies the postcondition of build_max_heap (which should be expressed in terms of is_heap).

## 5.8.4. Exercise 4¶

Implement in OCaml and check the invariant of the for-loop of heapsort. How does it imply the postcondition (i.e., that the whole array is sorted)? Hint: how does it relate the elements of the original array (you might need a copy of it), the sub-array before heap-size and the sub-array beyond the heap_size?

## 5.8.5. Exercise 5¶

Reimplement the heapsort, so it would work with a min-heaps instead of max-heaps. For this, you might also reimplement or, better, generalise the prior definitions of the Heap module.

## 5.8.6. Exercise 6¶

Implement and test the invariant for the while-loop of Radix Sort.