IC312: Data Structures (FA17)

Home Policy Calendar Units Assignments Resources

HW 7: Heaps

Overview

This is a written homework assignment. It is due in class, in hard-copy.

Due Date

This homework is due Mon. 30 Oct. in class

Grading

The assignment is graded out of 100 points. Each question is worth 20 points.

Submission and Starter Code

Submission must occur in hard copy at the start of class.

Problems

  1. For the following heap, draw the tree state after inserting 13, 88, 42, and 18. Provide the tree state after each insertion.

    prob1.png

  2. Write down the array that would store the following heap:

    prob2.png

  3. For the following two arrays, draw the heap that is represented by those arrays:
    1. [ 81, 64, 74, 40, 1, 48, 10, 30]
    2. [ 33, 3, 11, 1 , 0, 5, 7]
    3. [ 95, 81, 37, 45, 42, 10, 5, 13, 12, 0, 3]

  4. Starting with the following array based heap, show the array after each insertion. (Insertions are cumulative, so in (b) 20 was already inserted). Be sure to clearly indicate the array after each insertion.

    [82, 41, 79, 39, 15, 46, 49, 38]

    1. insert(20)
    2. insert(60)
    3. insert(85)

  5. (20 points) Starting with the following array-based heap, show the resulting array after performing the following series of removals. You can show any of your work, but be sure to clearly indicate the array after each removal.

    [ 93, 63, 87, 50, 61, 78, 35, 38, 40, 6, 26]

    1. removeMax()
    2. removeMax()
    3. removeMax()