Back to Study Material Python

Heapq

The heapq module provides functions that implement a min-heap using a regular Python list. A heap is a binary tree where every parent is smaller than or eq...

Heapq

What is heapq?

The heapq module provides functions that implement a min-heap using a regular Python list. A heap is a binary tree where every parent is smaller than or equal to its children (min-heap property). The heap is represented as a list where the smallest element is always at index 0. import heapq; heap = []; heapq.heappush(heap, 5); heapq.heappush(heap, 3); heapq.heappop(heap) returns 3. The module does not provide a separate Heap class; all operations act on a plain list.

Core heapq Operations

heappush(heap, item) pushes an item onto the heap. heappop(heap) removes and returns the smallest item, maintaining the heap invariant. heappushpop(heap, item) pushes item then pops the smallest — more efficient than separate push and pop. heapreplace(heap, item) pops the smallest and pushes item — the item can be larger than what was popped, unlike heappushpop. heapify(lst) converts an existing list to a heap in O(n) time (faster than pushing each element one by one).

nlargest and nsmallest

heapq.nlargest(n, iterable) and heapq.nsmallest(n, iterable) return the n largest or smallest elements as a list. heapq.nlargest(3, [5, 1, 8, 3, 9, 2]) gives [9, 8, 5]. Both accept a key function: heapq.nlargest(2, students, key=lambda s: s.gpa). For small n relative to the data size, these are efficient because they use a heap of size n. For n close to the total count, sorting and slicing may be equally fast.

Simulating a Max-Heap

Python only provides a min-heap. To simulate a max-heap, negate the values on push and negate them again on pop: heapq.heappush(heap, -value); max_val = -heapq.heappop(heap). For complex objects, store tuples of (-priority, item) so the comparison uses the negated priority first. This pattern is widely used in priority queue implementations, Dijkstra's algorithm, and scheduling tasks by priority.

Priority Queue with heapq

A common use of heapq is implementing a priority queue: tasks = []; heapq.heappush(tasks, (1, "low priority task")); heapq.heappush(tasks, (0, "urgent task")); priority, task = heapq.heappop(tasks) gives (0, "urgent task") — the task with the lowest priority number (highest urgency) first. When priorities are equal, tuples compare the next element (the task string). To avoid comparing task strings, add a tie-breaking counter as the second tuple element.

Exam Tip

Key heapq exam facts: heapq implements a min-heap (smallest element first). It operates on regular Python lists — there is no Heap class. heapify() is O(n); repeated heappush is O(n log n), so always use heapify() to convert an existing list. The typical interview question involving heapq: find the k-th largest element. Answer: use heapq.nlargest(k, data)[-1] or maintain a min-heap of size k. Knowing the time complexity (push/pop is O(log n)) and when to choose heapq over sorting is essential.