Backend / Algorithms & data structures / Python specific / 01_bisect_heapq_deque_patterns.md

Python-specific patterns: bisect, heapq, deque

Updated 5 interview angles 5 min read source
On this page6
  1. bisect — sorted list operations
  2. heapq — min-heap
  3. deque — double-ended queue
  4. Performance reference
  5. When to reach for what
  6. Interview angle

Python-specific patterns: bisect, heapq, deque

Three stdlib modules that turn many DSA problems into one-liners.

bisect — sorted list operations

bisect_left(arr, x) returns where x would go to keep arr sorted. bisect_right returns the rightmost such position. insort inserts in O(log n) lookup + O(n) shift.

python 
import bisect

arr = [1, 3, 5, 7, 9]
bisect.bisect_left(arr, 6)    # 3 — would go at index 3
bisect.insort(arr, 6)         # arr is now [1, 3, 5, 6, 7, 9]

Pattern: count elements in range [lo, hi]

python 
def count_in_range(sorted_arr, lo, hi):
    return bisect.bisect_right(sorted_arr, hi) - bisect.bisect_left(sorted_arr, lo)

Pattern: longest increasing subsequence (O(n log n))

python 
import bisect

def lis_length(nums):
    tails = []
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Pattern: nearest value in a sorted array

python 
def nearest(arr, target):
    i = bisect.bisect_left(arr, target)
    candidates = []
    if i > 0: candidates.append(arr[i-1])
    if i < len(arr): candidates.append(arr[i])
    return min(candidates, key=lambda x: abs(x - target))

heapq — min-heap

Python’s heapq is a min-heap. heappush/heappop are O(log n). Use negative values for max-heap.

python 
import heapq

h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
heapq.heappush(h, 2)
heapq.heappop(h)    # 1 (smallest first)

# Max-heap via negation:
max_h = []
heapq.heappush(max_h, -3)
heapq.heappush(max_h, -1)
-heapq.heappop(max_h)    # 3

For non-numeric items, push tuples: heappush(h, (priority, item)).

heapq.heapify — convert list to heap in O(n)

python 
items = [5, 1, 3, 9, 2]
heapq.heapify(items)    # in-place, O(n)
heapq.heappop(items)    # 1

heapq.nlargest / nsmallest

python 
heapq.nlargest(3, [1, 8, 4, 7, 2, 9])   # [9, 8, 7]
heapq.nsmallest(2, words, key=len)       # 2 shortest words

For small k, use these. For k = n, use sorted instead. They use a heap of size k, O(n log k).

Pattern: K-th largest element

python 
def kth_largest(nums, k):
    return heapq.nlargest(k, nums)[-1]

Alternative — maintain a min-heap of size k; the root is the K-th largest:

python 
def kth_largest_heap(nums, k):
    h = []
    for x in nums:
        heapq.heappush(h, x)
        if len(h) > k:
            heapq.heappop(h)
    return h[0]

O(n log k). Good when n is huge and k is small (top-K from streaming data).

Pattern: merge K sorted lists

python 
import heapq

def merge_k_sorted(lists):
    return list(heapq.merge(*lists))   # stdlib does it

Or build manually with a heap of (value, list_idx, item_idx):

python 
def merge_manual(lists):
    h = []
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(h, (lst[0], i, 0))
    result = []
    while h:
        val, i, j = heapq.heappop(h)
        result.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(h, (lists[i][j+1], i, j+1))
    return result

Pattern: median of a stream

Two heaps: max-heap of lower half, min-heap of upper half. Median is top of either (or average).

python 
class MedianStream:
    def __init__(self):
        self.lo = []   # max-heap (negated)
        self.hi = []   # min-heap
    
    def add(self, x):
        heapq.heappush(self.lo, -x)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
    
    def median(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

deque — double-ended queue

O(1) append/pop on both ends. Use for queues (BFS), sliding windows, recent-items buffers.

python 
from collections import deque

q = deque([1, 2, 3])
q.append(4)         # [1, 2, 3, 4]
q.appendleft(0)     # [0, 1, 2, 3, 4]
q.pop()             # 4
q.popleft()         # 0
q.rotate(1)         # rotate right

Pattern: sliding window maximum

python 
from collections import deque

def max_sliding_window(nums, k):
    """Max in every window of size k."""
    # holds indices; values in decreasing order
    q = deque()
    result = []
    for i, x in enumerate(nums):
        while q and nums[q[-1]] <= x:
            q.pop()
        q.append(i)
        if q[0] <= i - k:
            q.popleft()
        if i >= k - 1:
            result.append(nums[q[0]])
    return result

The deque stores indices of candidates for max, in decreasing order of value. Front is always the max of the current window.

Pattern: BFS

python 
from collections import deque

def bfs(start, neighbors):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        process(node)
        for n in neighbors(node):
            if n not in visited:
                visited.add(n)
                q.append(n)

Pattern: bounded recent history

python 
# auto-evicts oldest when full
recent = deque(maxlen=100)

for event in stream:
    recent.append(event)
    # `recent` always holds the last 100

Performance reference

Operation list deque heap (heapq)
append end O(1) amortized O(1) O(log n)
append front O(n) O(1) —
pop end O(1) O(1) —
pop front O(n) O(1) O(log n)
min/max O(n) O(n) O(1) (root only)
insert sorted O(n) O(n) O(log n)
access by index O(1) O(n) —

bisect.insort keeps a plain list sorted: O(log n) to find the position, then O(n) to shift the tail, and index access stays O(1) because it is still a list.

When to reach for what

  • Need ordered insertion + range queries → bisect on a sorted list (or use a balanced BST library like sortedcontainers.SortedList).
  • Need top-K, K-th smallest, priority queue → heapq.
  • Need a queue (FIFO) or sliding window → deque.
  • Need a sorted set / multiset with O(log n) all operations → sortedcontainers.SortedList (third-party).
  • Need O(1) random access AND sorted order — there’s no built-in. Pick the operations that matter most.

Interview angle 5

  • “How would you implement a priority queue in Python?” - heapq, which is a min-heap operating on a plain list. For a max-heap, push negated values - Python has no max-heap and inverting the key is the idiom.
  • “How do you find the median of a stream?” - two heaps: a max-heap of the lower half and a min-heap of the upper half, rebalanced so their sizes differ by at most one. The median is then a peek, in constant time, with logarithmic inserts.
  • “What gives you sliding window maximum in linear time?” - a monotonic deque holding indices, popping from the back anything smaller than the incoming value and from the front anything that has left the window. Each index enters and leaves once, so it is O(n) rather than O(n·k).
  • “How do you find where a value belongs in a sorted list?” - bisect, and know both ends: bisect_left gives the first position it could occupy, bisect_right the last.
    • Follow-up: “What is that difference good for?” - counting. The gap between bisect_right and bisect_left is how many times the value occurs, found in two logarithmic lookups rather than a scan.
  • “How do you get the top K from a billion records?” - a min-heap capped at size K, pushing and popping as you stream. Memory is O(K) rather than O(n), which is the entire point when the data does not fit. heapq.nlargest is exactly this.