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.
Not a valid Binary Heap because the node with 7 has a value smaller than it (2) as a child.
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.
Not a valid Binary Heap because it is not a complete tree.
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.
The value returned is 5, because the minimum value is always stored at the top of the heap.
When doing removeMin
, we do a percolateDown
operation. Recall the process for removeMin
is:
percolateDown
that node to restore the Heap invariantThis 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.