Section 4.5.2 describes a way of storing a complete binary tree of n nodes in an array ind...

Section 4.5.2 describes a way of storing a complete binary tree of n nodes in an array indexed by 1, 2, . . . , n.

(a) Consider the node at position j of the array. Show that its parent is at position ⌊ j/2⌋ 0xfb and its children are at 2 j and 2 j + 1 (if these numbers are ≤ n).

(b) What are the corresponding indices when a complete d-ary tree is stored in an array?

Figure 4.16 shows pseudocode for a binary heap, modeled on an exposition by R. E. Tarjan.2 The heap is stored as an array h, which is assumed to support two constant-time operations:

• |h|, which returns the number of elements currently in the array;

• h-1, which returns the position of an element within the array.

The latter can always be achieved by maintaining the values of h-1 as an auxiliary array.

(c) Show that the makeheap procedure takes O(n) time when called on a set of n elements. What is the worst-case input? (Hint: Start by showing that the running time is at most

(d) What needs to be changed to adapt this pseudocode to d-ary heaps?

Figure 4.16 Operations on a binary heap.