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:
print(heap.heap_list) # Outputs: [None, 99, 22, 61, 10, 21, 13, 23]
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,
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
print(heap.heap_list) # Outputs: [None, 99, 22, 61, 10, 21, 13, 23] heap.retrieve_max() # Returns: 99 print(heap.heap_list) # Outputs: [None, 23, 22, 61, 10, 21, 13]
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.
.retrieve_max() method within our
MaxHeap class. Its only parameter is
Inside the method, check if
count is equal to
0. If the condition is
"No items in heap" and return
if statement, declare the variable
max_val, which is the element at index
1 in the
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.
1 and remove the last element from the list using
Print the message
"Last element moved to first: [self.heap_list]".
Finally, return the
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.