This lesson's interactive features are locked, please to keep using them

Pop

To complete our min heap, we need to be able to remove the minimum element. This is called a pop operation. It's a bit more complicated than push because we need to maintain the tree structure.

Min Heap Visualization

Again, for reference, here's a visualization of a min heap:

And here's the array representation:

[8, 10, 9, 21, 31, 27, 12, 58, 99, 42, 33, 39]

Assignment

Complete the pop method and its helper method, bubble_down.

pop(self) -> tuple[int, str] | None
1. If there are no elements in the heap, return None.
2. If there is only one element in the heap (the root element), remove and return it.
3. Otherwise, save the root element (the entire tuple) in a variable so you can return it once you're done bubbling.
4. Pop the last element from the list – i.e., a normal pop – and replace the current root element (index 0) with it.
5. Call bubble_down with the index of the root element.
6. Return the saved tuple of the original root element.
bubble_down(self, index: int) -> None
1. Calculate the index of the left child of the given index.
2. Calculate the index of the right child of the given index.
3. Find the index of the child with the smallest priority. Remember to check whether the child index actually exists.
4. If there's a child with a smaller priority, swap the parent and that child and recursively call bubble_down.

Note: bubble_down does not return a value.