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 idoes not restore a heap, unless run recursively.
max_heapifyso 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
5.8.4. Exercise 4¶
Implement in OCaml and check the invariant of the
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
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