Heappop Function Of Heapq Module In Python

Overview:

  • The functions of the heapq module enable construction and manipulation of min heaps.
  • The heap is constructed as a binary tree. In a min heap the smallest element is at the root. The child nodes store values greater than the parent nodes.
  • The heappop() function removes and returns the smallest element from the heap.
  • As heappop() is called it removes and returns the root node of a min heap and invalidates the heap to maintain the heap invariant.

Example:

# Example Python program that removes smallest element(s) from a

# min heap using heappop() function

import heapq

 

# Construct a heap

heapElements = ["a", "d", "b", "g", "e", "c", "f" ]

print("Original list:%s"%heapElements)

 

heapq.heapify(heapElements)

print("Result of calling heapq.heapify():%s"%heapElements)

print(heapElements)

 

# Remove the smallest element from the heap

smallest = heapq.heappop(heapElements)

print("Smallest element:%s"%smallest)

print("Updated heap:%s"%heapElements)

 

# Remove the current smallest element

smallest = heapq.heappop(heapElements)

print("Currently the smallest element is:%s"%smallest)

print("Updated heap:%s"%heapElements)

 

Output:

Original list:['a', 'd', 'b', 'g', 'e', 'c', 'f']

Result of calling heapq.heapify():['a', 'd', 'b', 'g', 'e', 'c', 'f']

['a', 'd', 'b', 'g', 'e', 'c', 'f']

Smallest element:a

Updated heap:['b', 'd', 'c', 'g', 'e', 'f']

Currently the smallest element is:b

Updated heap:['c', 'd', 'f', 'g', 'e']

Min heap before calling heappop()

After calling heappop()

MIn heap After calling heapq.heappop() twice

 


Copyright 2022 © pythontic.com