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
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
For the following heap, draw the tree state after inserting 13, 88, 42, and 18. Provide the tree state after each insertion.
Write down the array that would store the following heap:
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]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)(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()