How to Implement Heap in Python: Syntax and Examples

In Python, you can implement a heap using the heapq module which provides functions to create and manipulate a min-heap. Use heapq.heappush() to add items and heapq.heappop() to remove the smallest item efficiently.

Syntax

The heapq module provides these main functions:

• heapq.heapify(list): Converts a list into a heap in-place.
• heapq.heappush(heap, item): Adds an item to the heap, maintaining heap order.
• heapq.heappop(heap): Removes and returns the smallest item from the heap.

The heap is represented as a list where the smallest element is always at index 0.

python

import heapq

heap = []  # empty list to use as heap
heapq.heappush(heap, 10)  # add 10
heapq.heappush(heap, 5)   # add 5
heapq.heappush(heap, 20)  # add 20
smallest = heapq.heappop(heap)  # removes and returns 5

Example

This example shows how to create a heap from a list, add new items, and pop the smallest item.

python

import heapq

numbers = [20, 15, 10, 30, 40]
heapq.heapify(numbers)  # turn list into a heap

print('Heap:', numbers)

heapq.heappush(numbers, 5)  # add 5
print('After heappush(5):', numbers)

smallest = heapq.heappop(numbers)  # remove smallest
print('Smallest item popped:', smallest)
print('Heap after pop:', numbers)

Output

Heap: [10, 15, 20, 30, 40]
After heappush(5): [5, 15, 10, 30, 40, 20]
Smallest item popped: 5
Heap after pop: [10, 15, 20, 30, 40]

Common Pitfalls

Common mistakes when using heaps in Python include:

• Forgetting to call heapq.heapify() before using heappop() on a normal list.
• Using heappush() on a list that is not a heap, which breaks the heap property.
• Expecting a max-heap behavior; heapq only supports min-heaps by default.

To create a max-heap, you can invert the values by pushing their negatives.

python

import heapq

# Wrong: popping from a normal list without heapify
numbers = [10, 20, 15]
# smallest = heapq.heappop(numbers)  # This will raise an IndexError

# Right: heapify first
heapq.heapify(numbers)
smallest = heapq.heappop(numbers)
print('Smallest after heapify:', smallest)

# Max-heap example by pushing negative values
max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -20)
heapq.heappush(max_heap, -5)
max_item = -heapq.heappop(max_heap)
print('Max item:', max_item)

Output

Smallest after heapify: 10
Max item: 20

Quick Reference

Function	Description
heapq.heapify(list)	Convert list into a heap in-place
heapq.heappush(heap, item)	Add item to heap maintaining order
heapq.heappop(heap)	Remove and return smallest item
heapq.heappushpop(heap, item)	Push then pop smallest item efficiently
heapq.heapreplace(heap, item)	Pop smallest then push new item

Key Takeaways

Use the heapq module to implement heaps easily in Python.

Always call heapq.heapify() on a list before popping items to maintain heap property.

heapq implements a min-heap; invert values to simulate a max-heap.

Use heappush() to add items and heappop() to remove the smallest item efficiently.

heapq provides extra functions like heappushpop() and heapreplace() for optimized operations.