Hands-On Data Structures and Algorithms with Python - Second Edition

Pop operation

The pop operation removes an element from the heap. The reason for removing an element from the min-heap is, first, to find out the index of the item to be deleted, and then organize the heap so that it satisfies the heap property. However, it is more common to pop off the minimum value from the min-heap, and as per the property of the min-heap, we can get the minimum value by its root value. Therefore, to obtain and remove the minimum value from the min-heap, we remove the root node and re-organize all the nodes of the heap. We also decrement the size of the heap by one.

However, once the root has been popped off, we need a new root node. For this, we just take the last item from the list and make it the new root. That is, ...