Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.

We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.

Question 2

1. Not a valid Binary Heap because the node with 7 has a value smaller than it (2) as a child.

   

2. This is a valid Binary Heap since it satisfied all the invariants. A common concern is the fact that there are duplicate values, which is not a problem in the heap invariants.

   

3. Not a valid Binary Heap because it is not a complete tree.

   

4. Not a valid Binary Heap because it is not a complete tree. Notice the row at index 2 is not completely full but the tree already started a row at index 3.

   

Question 3

Question 3.1

The value returned is 5, because the minimum value is always stored at the top of the heap.

Question 3.2

When doing removeMin, we do a percolateDown operation. Recall the process for removeMin is:

1. Remove the value from the top of the tree (to return at the end)
2. Grab the last node at the bottom-level of the tree and move it to the top
3. percolateDown that node to restore the Heap invariant

Question 3.3

This one is a bit weird since we asked for this strange-looking format. The correct answer is [7,8,7,13,9,11,15] which corresponds to the following tree:

To get this answer, we start by following the removeMin algorithm.