CMPS 144L: Lab Activity on Max-Heaps

A Max-Heap

37 / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ 30 26 / \ / \ / \ / \ / \ / \ / \ / \ 15 24 20 12 /\ /\ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ 8 2 5 17 16 13 3 0 / \ / / \ / 6 4 0

A max-heap (with only keys visible) is shown to the right. Space in which to provide answers to the following problems is found below.

1. Show the contents of an array that represents the heap pictured above, in accord with the standard scheme by which an array is mapped to a complete binary tree.

Because the size of a heap can grow and shrink over time, but an array's length remains fixed, an array will typically have a length that exceeds the current size of the heap that it represents. Thus, a numNodes variable is also needed in the concrete representation. (Here, we suppose that the array has length 20, even though the heap has fewer elements.)

2. Carry out the following operations in succession, for each one showing how the heap has changed as a result. (Here it suffices to show only the nodes along the path where changes have occurred, perhaps with a little surrounding context.)

(a) insert(18)       (b) insert(32)

3. Revert back to the original heap, as pictured above, and carry out the following operations in succession, for each one showing how the heap has changed (just as you did in the previous problem).

(a) deleteMax()       (b) deleteMax()

Answers:

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 numNodes +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ +------+ 1. | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+ +------+

Use the rest of the page (and back, if needed) for your answers to Problems 2 and 3.