Bird
Raised Fist0
PythonHow-ToBeginner · 3 min read

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

FunctionDescription
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.