A binary tree that keeps the smallest (min-heap) or largest (max-heap) element at the root. Insert/extract in O(log N); look-up of top in O(1).

Data Flow (min-heap)

[1, 3, 6, 5, 9, 8]

        1
      /   \
     3     6
    / \   /
   5   9 8

parent(i) = (i-1)//2;   left(i) = 2*i+1;   right(i) = 2*i+2

When to use

• Streaming top-K / Kth largest.
• Merge K sorted lists.
• Dijkstra’s shortest path (min-heap keyed on distance).

Code (top K frequent)

from collections import Counter
import heapq
 
def top_k_frequent(nums, k):
    freq = Counter(nums)
    return [n for n, _ in heapq.nlargest(k, freq.items(), key=lambda x: x[1])]

Code (running median, two heaps)

import heapq
 
class MedianFinder:
    def __init__(self):
        self.lo = []   # max-heap (store negatives)
        self.hi = []   # min-heap
 
    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.lo) < len(self.hi):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
 
    def find(self):
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

Pitfalls

• Python’s heapq is a min-heap. Use -value for max-heap semantics.
• Forgetting to rebalance after heappop.

Analogy

A hospital triage queue: most urgent always gets seen next, regardless of arrival order.

Interview tip: Two heaps (max + min) are the canonical way to compute the running median in O(log N) per insert.