Our goal is to efficiently remove the maximum element from the heap in order to place it inside of our sorted list. We’ll accomplish this task by creating a .retrieve_max() method that does the following:
- Swaps the first and last element.
- Removes and returns the largest value.
- Rebalances the existing heap.
Take a look at our example heap:
Our internal list mirrors a binary tree. There’s a delicate balance of parent and child relationships we would ruin by directly removing the maximum element, 99.
The solution to this problem is to swap the first and last element. The last element in a heap has no children so we can remove it without disrupting our binary tree structure.
Let’s see this in action. Note how the last element 23 becomes the first element in the heap list after calling .retrieve_max():
Terrific! We removed the maximum element with minimal disruption. Unfortunately, our heap is out of shape again with 23 sitting where the maximum element should be.
We’ll learn how to rebalance our heap in the next lesson.
Instructions
Define a .retrieve_max() method within our MaxHeap class. Its only parameter is self.
Inside the method, check if count is equal to 0. If the condition is true, print "No items in heap" and return None.
Outside the if statement, declare the variable max_val, which is the element at index 1 in the heap_list.
Print the message "Removing: [max_val] from [self.heap_list]".
Set the value at index 1 to self.heap_list[self.count]. This will replace the value of the first element with the value of the last element.
Afterward, decrement count by 1 and remove the last element from the list using .pop().
Print the message "Last element moved to first: [self.heap_list]".
Finally, return the max_val variable.
Tab over to script.py and run the test code to see .retrieve_max() in action.
When we run this code, the output will look a little strange since we never rebalance our heap. Don’t worry - we’ll fix this over the next two exercises.