Heaps

Overview

A heap is a tree-based structure that keeps the smallest (min-heap) or largest (max-heap) element at the root, making peek O(1). Pushing and popping cost O(log n) because the tree re-balances along one path. Python's heapq module implements a min-heap on top of a regular list, which is ideal for priority queues.

Syntax / Usage

Use heapq functions on a plain list.

import heapq

heap = []
heapq.heappush(heap, 5)   # O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)

smallest = heap[0]        # peek min -> O(1) -> 1
value = heapq.heappop(heap)  # remove min -> O(log n) -> 1

nums = [9, 2, 7, 4]
heapq.heapify(nums)       # build heap in O(n)
print(nums[0])            # 2

Examples

Find the 3 smallest numbers efficiently:

import heapq

data = [8, 2, 11, 5, 1, 9]
print(heapq.nsmallest(3, data))  # [1, 2, 5]

Use a heap as a priority queue with (priority, task) tuples:

import heapq

tasks = []
heapq.heappush(tasks, (2, "email"))
heapq.heappush(tasks, (1, "deploy"))   # lower number = higher priority
heapq.heappush(tasks, (3, "cleanup"))

while tasks:
    priority, name = heapq.heappop(tasks)  # O(log n)
    print(priority, name)
# 1 deploy / 2 email / 3 cleanup

Common Mistakes

• Assuming the whole list is sorted — only the root is guaranteed smallest
• Reading heap[-1] expecting the largest element; it is not sorted
• Forgetting heapq is a min-heap; negate values to simulate a max-heap
• Indexing into the heap instead of using heappop to get items in order
• Calling heappop on an empty heap, raising IndexError

See Also

data-structures-trees data-structures-queues data-structures-arrays