CS 10C Programming Concepts and Methodologies 2

1. Draw the array that represents the maxheap shown in Figure 1.

2. Draw the array that represents the minheap shown in Figure 2.

3. If items is an array representing a heap, what criterion can you use to tell whether the node in items[i] is a leaf?

4. Draw the complete binary tree represented by the following array: 5 1 2 8 6 10 3 9 4 7

5. Does the array in the previous question represent a heap?

6. Consider the maxheap in Figure 1. Draw the heap after you insert 12 and then remove 12.

7. Assuming myHeap starts off empty, draw the max heap that results after the following sequence of pseudocode operations:

     myHeap.add(2)
     myHeap.add(3)
     myHeap.add(4)
     myHeap.add(1)
     myHeap.add(9)
     myHeap.remove()
     myHeap.add(7)
     myHeap.add(6)
     myHeap.remove()
     myHeap.add(5)

8. Consider a heap-based implementation of the ADT priority queue. What does the underlying heap contain after the following sequence of pseudocode operations, assuming that pQueue is an initially empty priority queue? (Higher numbers have higher priority.)

    pQueue.add(5)
    pQueue.add(9)
    pQueue.add(6)
    pQueue.add(7)
    pQueue.add(3)
    pQueue.add(4)
    pQueue.remove()
    pQueue.add(9)
    pQueue.add(2)
    pQueue.remove()

9. Given the minheap myHeap in figure 3, show what it would look like after each of the following pseudocode operations is executed in sequence.

    a. myHeap.add(8) 
    b. myHeap.add(5)
    c. myHeap.remove()

10. Given the maxheap myHeap in figure 4, show what it would look like after each of the following pseudocode operations is executed in sequence.

    a. myHeap.add(16) 
    b. myHeap.add(14) 
    c. myHeap.remove()