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

Python-specific patterns: bisect, heapq, deque

Updated 4 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) bisect.insort
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) O(log n) lookup + O(n) shift
arbitrary access by index O(1) O(n) — O(1) (it’s 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

“Implement a priority queue” → heapq. “Stream median” → two heaps. “Sliding window max” → monotonic deque. “Find insertion point” → bisect. “Top-K from a billion records” → min-heap of size K.