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 ?ni = 1 log(n/i).

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

Figure 4.16

Transcribed Image Text:

procedure insert (h, x) bubbleup (h, x, h| + 1) procedure decreasekey (h, x) bubbleup (h, x, h−¹(x)) function deletemin (h) if |h|=0: return null else: x = h(1) siftdown (h, h(|h|), 1) return x function makeheap (S) h = empty array of size |S| for x = S: h(|h| + 1) = x for i= |S| down to 1: siftdown (h, h(i), i) return h procedure bubbleup (h, x, i) (place element x in position i of h, and let it bubble up) p = [1/2] while i 1 and key (h(p)) > key (x): h(i)=h(p); i = p; p = [i/21 h(i) = x procedure siftdown (h, x, i) (place element x in position i of h, and let it sift down) c = minchild(h, i) while c 0 and key (h(c)) function minchild (h, i) (return the index of the smallest child of h(i)) if 2i> |hl: return 0 (no children) else: return arg min(key (h(j)) : 2i ≤ j≤min{|h], 2t + 1}} procedure insert (h, x) bubbleup (h, x, h| + 1) procedure decreasekey (h, x) bubbleup (h, x, h−¹(x)) function deletemin (h) if |h|=0: return null else: x = h(1) siftdown (h, h(|h|), 1) return x function makeheap (S) h = empty array of size |S| for x = S: h(|h| + 1) = x for i= |S| down to 1: siftdown (h, h(i), i) return h procedure bubbleup (h, x, i) (place element x in position i of h, and let it bubble up) p = [1/2] while i 1 and key (h(p)) > key (x): h(i)=h(p); i = p; p = [i/21 h(i) = x procedure siftdown (h, x, i) (place element x in position i of h, and let it sift down) c = minchild(h, i) while c 0 and key (h(c)) function minchild (h, i) (return the index of the smallest child of h(i)) if 2i> |hl: return 0 (no children) else: return arg min(key (h(j)) : 2i ≤ j≤min{|h], 2t + 1}}

Answer rating: 100% (QA)

a If the node at position j is the ith node on the kth level of the binary tree we have j 2 k i1 Its ... View the full answer