The Heapq Module In Python

Overview:

  • The heapq module in Python provides functions for constructing and manipulating min heaps.
  • A min heap is a binary tree in which
    • The child nodes contain values that are greater than or equal to the value of the root node.
    • The root node has the smallest value.
    • The heap invariant is maintained as new elements are added to the heap
  • The heapq module has functions nsmallest(), nlargest() that return the specified number of largest elements or smallest elements from the heap.
  • The function merge() takes multiple sorted sequences and produces a sorted sequence.

 

Example: Construct a min heap from a Python list

import heapq

 

# Construct a min-heap

elements = [5, 15, 10, 45, 20, 30, 35, 25, 40, 50]

heapq.heapify(elements)

 

# Print the min heap

print("The min heap is:")

print(elements)

 

Output:

The min heap is:

[5, 15, 10, 25, 20, 30, 35, 45, 40, 50]

 


Copyright 2022 © pythontic.com