Week 6. The Heap

Problem 7.1 (Expanded from Textbook R-9.1) We discussed in- and post-order tree traversal last week. There is also pre-order traversal, where the parent node is processed before both subtrees. The pre-order rank of a node, is its number in the sequence of node visits in a pre-order traversal. I.e. you make a pre-order traversal and number the nodes in sequence.

Let $T$ be a binary tree where each node has a key equal to the preorder rank. What condition(s) must be satisfied for $T$ to be a heap?

Hint. Consider the following questions in order: (1) Draw an arbitrary tree and number the nodes. Is the heap property satisfied? (2) Would it hold for all such trees? (3) Which other properties does a heap have to satisfy?

Problem 7.2 Do Textbook R-9.2.

Problem 7.3 Do Textbook C-9.37.

Problem 7.4 Do Textbook C-9.46–47.

Problem 7.5 Do Textbook R-9.12.

Problem 7.6 Do Textbook C-9.25–26.

Problem 7.7 (Based on textbook P-9.48) Heapsort can be implemented in two different ways. The most straight-forward high-level implementation uses the Priority Queue ADT. All the elements are first inserted in the queue and then extracted in order, giving the sorted sequence (which can be stored in whatever data structure).

The alternative saves memory by sorting in-place. This requires access to the underlying concrete data structure, so that the same storage (usually an array) can be interpreted partly as a heap and partly as an array.

Implement both approaches and compare their practical running time. Do you see a difference? Is there an asymoptotic difference?