Heaps & Priority Queue

A heap is a tree-shaped structure built for one job: instantly knowing the smallest (or largest) element in a collection, even as elements are added and removed. Unlike a BST, it makes no promise about ordering elements relative to each other in general — only about which single element sits on top. That narrower promise is exactly what makes heap operations fast and predictable. Python's heapq module gives you this directly on a plain list — with one API quirk that catches almost everyone the first time: it only ever implements a min-heap.

Min-Heap vs Max-Heap

A min-heap keeps the smallest element at the root — every parent is smaller than or equal to both its children. A max-heap is the mirror image — every parent is bigger than or equal to both its children. Note this is a much weaker rule than the BST invariant: a heap says nothing about whether a node's left subtree is smaller than its right subtree, only about parent vs. child.

Python's heapq Module — Min-Heap Only, By Design

heapq operates directly on a regular Python list, treating it as a binary heap using the same array index arithmetic every heap uses (parent = (i - 1) // 2, left = 2*i + 1, right = 2*i + 2) — there's no separate heap class to instantiate. And critically: every function in heapq maintains the min-heap property only. There is no max_heapq and no flag to flip it.

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heapq.heappop(heap))  # 1 -- the smallest

Time complexity: O(log n) for both heappush (insert) and heappop (extract-min). Space complexity: O(n) to hold n elements.

import heapq

max_heap = []
for value in [5, 1, 3]:
    heapq.heappush(max_heap, -value)   # push the NEGATED value

print(-heapq.heappop(max_heap))    # 5 -- negate again on the way out to undo it

Time complexity: O(log n) — identical cost to the min-heap version; negation is O(1) extra work per push/pop. Space complexity: O(n).

heappush, heappop, and heapify

Besides pushing one element at a time, heapq can convert an existing list into a valid heap in-place, all at once, faster than pushing each element individually.

import heapq

# heapify: turn an existing list into a valid min-heap in-place
nums = [5, 3, 8, 1, 9, 2]
heapq.heapify(nums)
print(nums)              # [1, 3, 2, 5, 9, 8] -- valid heap order, NOT fully sorted

# heappush: add one element, re-establishing the heap property
heapq.heappush(nums, 0)
print(nums[0])          # 0 -- new minimum bubbled to the root

# heappop: remove and return the smallest element
smallest = heapq.heappop(nums)
print(smallest)        # 0

# heapq also has direct helpers for the "top K" pattern:
print(heapq.nsmallest(3, nums))  # 3 smallest values, sorted ascending
print(heapq.nlargest(3, nums))   # 3 largest values, sorted descending

Time complexity: heapify is O(n) — a common surprise, since it sounds like it should cost O(n log n) (n pushes at O(log n) each), but a bottom-up build only needs O(n) total comparisons because most nodes are near the bottom of the tree and need very few swaps. heappush/heappop are O(log n) each. Space complexity: O(1) extra for heapify (it reorders the existing list), O(n) overall to hold the heap.

Worked Problem: Kth Largest Element

A classic heap problem: given an unsorted list, find the Kth largest element without fully sorting the list. The elegant approach uses a min-heap of size K: keep only the K largest elements seen so far, and the smallest of those K (the heap's root) is always the Kth largest overall.

import heapq

def find_kth_largest(nums, k):
    min_heap = []

    for num in nums:
        heapq.heappush(min_heap, num)
        if len(min_heap) > k:
            heapq.heappop(min_heap)      # evict the current smallest -- it can't be a top-K element

    return min_heap[0]                  # root of the size-k min-heap = Kth largest overall

print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5

Trace on nums = [3, 2, 1, 5, 6, 4], k = 2 (find the 2nd largest): push 3 → heap {3}. push 2 → heap {2,3}. push 1 → heap {1,2,3}, size > 2, pop evicts 1 → heap {2,3}. push 5 → heap {2,3,5}, size > 2, pop evicts 2 → heap {3,5}. push 6 → heap {3,5,6}, size > 2, pop evicts 3 → heap {5,6}. push 4 → heap {4,5,6}, size > 2, pop evicts 4 → heap {5,6}. Final min_heap[0] is 5 — correctly the 2nd largest value in the list (largest is 6).

Time complexity: O(n log k) — n pushes, each costing O(log k) since the heap never grows past size k (this beats the O(n log n) of fully sorting when k is small). Space complexity: O(k) — the heap never holds more than k elements at once.