DSA Interview Prep · Lesson

Python heapq and Max-Heap Tricks

Use heapq.heappush/heappop, negate values to simulate a max-heap, and apply heapq.nlargest/nsmallest for quick top-k queries.

Python's heapq Module Overview

Python's heapq module provides a min-heap implemented on top of a regular Python list. Unlike a dedicated heap class, heapq operates on existing lists in-place. The module functions are: heapify to build a heap in O(n), heappush to add an element in O(log n), heappop to remove the minimum in O(log n), and heappushpop / heapreplace for combined efficiency.

import heapq

# heapq operates on plain Python lists
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 1)

print('Heap array:', heap)          # internal array (not sorted!)
print('Peek min:', heap[0])         # O(1) min access
print('Pop min:', heapq.heappop(heap))  # 1
print('Next min:', heap[0])         # 2

# heapify: turn any list into a heap in O(n)
data = [9, 4, 7, 1, 3, 6, 2]
heapq.heapify(data)
print('Heapified:', data, '| min:', data[0])

Max-Heap by Negating Values

Python's heapq only provides a min-heap. To simulate a max-heap, negate all values before pushing and negate again when popping. This works because the heap orders by the stored values, and negating inverts the ordering. Always remember to negate on both sides: negate before push, negate after pop. Forgetting either step is a common interview bug.

import heapq

max_heap = []
for val in [5, 1, 8, 3, 9, 2]:
    heapq.heappush(max_heap, -val)  # negate on push

print('Max-heap internal:', max_heap)  # all negated

# Pop in descending order:
results = []
while max_heap:
    results.append(-heapq.heappop(max_heap))  # negate on pop
print('Sorted descending:', results)  # [9, 8, 5, 3, 2, 1]

# Common pattern: top-k largest
data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
k = 3
heap = []
for x in data:
    heapq.heappush(heap, -x)
print('Top', k, ':', [-heapq.heappop(heap) for _ in range(k)])

All lessons in this course

← Back to DSA Interview Prep