Odds and Ends.

a. Recall that heaps are implemented using arrays. In particular, because heaps make use of complete binary trees, we can label the nodes in a "natural way" using the numbers 1, 2, . . . , n where n is the number of items stored in the heap. If T is the said array, then T[i] contains the item associated with the ith node.

For now, let us assume that T[i].key and T[i].element are respectively the key and element associated with T[i]. We also discussed how to build heaps in a bottom-up fashion.

Assume T[1 · · · n] contains the n items. Below is the pseudocode I presented in class. BuildHeap(v) if v is an external node return else BuildHeap(v.lef tchild) if v.rightchild exists BuildHeap(v.rightchild) endif if v.key < v.lef tchild.key or v.key < v.rightchild.key DownHeapBubble(v) endif endif If we run BuildHeap(T.root) then T[1 · · · n] should be a heap at the end of the algorithm.

a1. Rewrite the above pseudocode so that it takes into account that T is actually an array. That is, instead of v, v.lef tchild and v.rightchild, the pseudocode should refer to the appropriate indices in T. Furthermore, write a procedure for DownHeapBubblev that also takes into account that T is an array.

a2. Demonstrate how the pseudocode you wrote in part (a) for BuildHeap(T.root) runs on the array T[1 · · · 9] whose keys are [22, 15, 36, 44, 10, 3, 9, 13, 29]. That is, show what happens to the array as you make each call to BuildHeap. 1

b. We said that a binary search tree is a binary tree that stores (key, element) pairs at its nodes. It satisfies the property that for every node v, v.key is greater than or equal to every key stored at v's left subtree and v.key is greater than or equal to every key stored at v's right subtree. I noted that this property cannot be weakened to for every node v, v.key = v.lef tchild.key and v.key = v.rightchild.key.

Convince yourself that what I said is indeed true. That is, create a binary tree that stores some (key, element) pairs and satisfies the weakened version of the property but is not a binary search tree.