Course Home | Course Policies | Homework | Lab Open Hours | Programming | Labs | Schedule & Lecture Notes

Homework Assignment 5

Trees and Heaps

Problems to be Submitted (30 points)

  1. (8 points)

    Assume that we start with an initially empty heap, and that items are inserted with the following sequence of integer keys:

    insert(20), insert(7), insert(8), insert(5), insert(12), insert(11), insert(6), insert(18), insert(14), insert(3), insert(4), insert(13).
    Using Figure 8.3 as a guide for style, draw the heap which results at the very end of the last operation.

    Note: for this problem we are not requiring you to show any of the work along the way, though you may if you wish. Please do be careful to follow the exact sequence given and to double-check your work.

  2. (2 points)

    In class, we wrote an array based implementation of heaps. Please draw the contents of an array which represents the tree T you gave in your answer to Problem A.

  3. (5 points)

    Now draw the heap that results after the operation removeMax() is called on your heap from Problem A.

  4. (5 points)

    A certain Professor CrazyBeard claims that a preorder traversal of a heap will list out the elements of the heap in sorted order, in the same way that binary search trees work. Draw a (small) example of a heap that proves him wrong.

  5. (5 points)

    For the tree in Figure 7.11 (on page 285), what order will nodes be visited during a preorder traversal?

  6. (10 points)

    Draw a (proper) binary tree T such that simultaneously,

  7. (5 points)

    Insert, into an initially empty binary search tree, items with the following keys (in this order): 33, 40, 24, 58, 49, 20, 63, 25, 11, 13. Draw the final tree after that order of insertions. (Again, you may wish to show your work along the way.)