# 5.8. Exercises¶

## 5.8.1. Exercise 1¶

Answer the following small questions about heaps:

- What is a maximal and a minimal number of elements in a heap of the height \(h\)? Explain your answer and give examples.
- Is an array that is sorted a min-heap?
- 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.