Heap

First PublishedFeb 11, 2026ByAtif Alam

Difficulty: Medium. ROI: Medium.

Other common names: Priority queue (abstract), binary heap, min-heap / max-heap.

When to use: Use when you need the smallest (or largest) element quickly, “kth largest,” “merge k sorted lists,” or “top K frequent.” Python: heapq for min-heap.

Idea: A heap keeps the min (or max) at the root. Insert and extract-min are O(log n). Often you only need a fixed-size heap of size k for “top K” problems.

Time / space: Insert and extract O(log n). Space O(n) for n elements.

Example #1 — Kth Largest

Keep a min-heap of size k containing the k largest elements seen so far. The root is the smallest of those, i.e. the kth largest. For each new element larger than the root, replace the root.

Sample input and output

arr = [3, 2, 1, 5, 6, 4]
k = 2
print(kth_largest(arr, k))  # 5  (2nd largest is 5; top two are 6, 5)

• Sample input: arr = [3, 2, 1, 5, 6, 4], k = 2.
• Sample output: 5 — the 2nd largest element is 5 (the largest is 6).

Code (with inline comments)

import heapq

# Kth largest: keep a min-heap of size k (smallest of top k at root)
def kth_largest(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    for x in arr[k:]:
        if x > heap[0]:       # x is larger than smallest in heap → belongs in top k
            heapq.heapreplace(heap, x)  # pop smallest, push x in one step
    return heap[0]

Line-by-line:

• import heapq — Python’s heapq module provides a min-heap: the smallest element is always at index 0. Operations like push and pop keep that invariant in O(log n) time.
• heapq.heapify(heap) — Rearranges the list in place so it satisfies the heap property (each parent ≤ its children). Takes O(n) time.
• heap = arr[:k] — For “kth largest,” we keep only the k largest elements we’ve seen. We start with the first k elements.
• if x > heap[0]: heapq.heapreplace(heap, x) — heapreplace pops the smallest and pushes the new element in one go. So we only add x if it’s bigger than the smallest in our “top k” heap; then we drop that smallest. After processing all elements, the smallest in the heap is the kth largest overall.

Execution trace (numbered list)

For arr = [3, 2, 1, 5, 6, 4], k=2:

1. Step 0: heap = [3,2], heapify → [2, 3]. (min at 0 = 2)
2. Step 1: x=1. 1 ≤ 2, skip. heap=[2, 3].
3. Step 2: x=5. 5 > 2, heapreplace → [3, 5].
4. Step 3: x=6. 6 > 3, heapreplace → [5, 6].
5. Step 4: x=4. 4 ≤ 5, skip. Return heap[0] = 5.

Execution trace (code with step comments)

arr = [3, 2, 1, 5, 6, 4]
k = 2
heap = arr[:k]   # [3, 2]
heapq.heapify(heap)   # [2, 3]
# x=1: 1 <= 2 → skip
# x=5: 5 > 2 → heapreplace → [3, 5]
# x=6: 6 > 3 → heapreplace → [5, 6]
# x=4: 4 <= 5 → skip
# return heap[0] = 5

Execution trace (ASCII diagram)

Min-heap of size 2: root is the 2nd largest. We replace the root when we see a larger value.

After heapify:     heap = [2, 3]     root=2 (2nd largest so far)
After x=5:         heap = [3, 5]     root=3
After x=6:         heap = [5, 6]     root=5 → return 5