# IC312: Data Structures (FA16)

Home Policy Calendar Units Assignments Resources

# HW 7: Heaps

## Solution

You can find the solution here

## Overview

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

### Due Date

This homework is due Wed. 2 Nov. in class

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.

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

3. For the following two arrays, draw the heap that is represented by those arrays:

a. [ 81, 64, 74, 40, 1, 48, 10, 30]

b. [ 33, 3, 11, 1 , 0, 5, 7]

c. [ 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]

a. insert(20)

b. insert(60)

c. 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]

a. removeMax()

b. removeMax()

c. removeMax()