heapq & bisect
Overview
When writing highly performant code (especially in algorithm interviews), maintaining sorted data is a common requirement. The heapq module provides a Min-Heap data structure implemented over a standard list. It allows you to constantly insert and retrieve the smallest item in O(log N) time, making it perfect for Priority Queues or 'Top K' problems. The bisect module provides binary search algorithms for finding insertion points in pre-sorted arrays, allowing you to maintain sorted order without resorting the entire array.
Syntax
import heapq
import bisect
# --- HEAPQ (Min-Heap) ---
nums = [5, 1, 9, 3]
heapq.heapify(nums) # Transforms list in-place to a heap: O(N) time
print(nums[0]) # 1 (The smallest element is ALWAYS at index 0)
heapq.heappush(nums, 2) # Adds 2 while maintaining heap structure: O(log N)
smallest = heapq.heappop(nums) # Removes and returns 1: O(log N)
# --- BISECT (Binary Search) ---
sorted_grades = [60, 70, 80, 90]
# Find where to insert 75 to keep the list sorted: O(log N) time
insert_index = bisect.bisect_left(sorted_grades, 75) # 2
# Insert it directly
bisect.insort(sorted_grades, 75)
print(sorted_grades) # [60, 70, 75, 80, 90]Common Pitfalls
- Assuming
heapq.heapify()fully sorts the array. It does NOT. A heap is a tree-based structure. While the rootnums[0]is guaranteed to be the absolute minimum, the rest of the array is only partially ordered. - Forgetting that
heapqonly provides a MIN-heap. If you need a MAX-heap (where the largest element is popped first), you must multiply all numbers by-1before pushing, and multiply by-1after popping.
Interview Questions
Instead of sorting the entire list (which takes O(N log N) time), use heapq.nlargest(3, my_list). Under the hood, this maintains a heap of size 3 and processes the list in a single pass, which is vastly faster.
Real-World Example
Building a task scheduler based on priority (lowest number = highest priority).
import heapq
task_queue = []
# Pushing tuples (priority_score, task_name)
heapq.heappush(task_queue, (3, "Write Docs"))
heapq.heappush(task_queue, (1, "Fix Critical Bug"))
heapq.heappush(task_queue, (2, "Review PR"))
# Automatically pops the tuple with the lowest priority_score first
priority, task = heapq.heappop(task_queue)
print(f"Executing: {task}") # Executing: Fix Critical BugCheck Your Knowledge
Test your understanding of heapq & bisect with these quick questions.