The heapq module in Python

The Python module heapq provides functions for creating a min heap and manipulating it by adding, removing elements to it. It also has functions for finding the specified number of smallest or largest elements in a min-heap.

Heapq Updated 3 Jan 2020 1 min read

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

python
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

Output
The min heap is:

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