Python Data Structures and Algorithms

Pop

Just like insert, pop() is by itself a simple operation. We remove the root node and decrement the size of the heap by one. However, once the root has been popped off, we need a new root node.

To make this as simple as possible, we just take the last item in the list and make it the new root. That is, we move it to the beginning of the list. But now we might not have the lowest element at the top of the heap, so we perform the opposite of the float operation: we let the new root node sink down as required.

As we did with insert, let us have a look at how the whole operation is meant to work on an existing heap. Imagine the following heap. We pop off the root element, leaving the heap temporarily rootless:

Since we cannot have a rootless ...