Heaps & Priority Queues: Complete Guide

Introduction

A heap is the data structure you reach for whenever you need fast access to the minimum or maximum element in a collection. It powers everything from Dijkstra's shortest-path algorithm (which you saw in Graphs & Graph Algorithms) to operating system task schedulers, event-driven simulations, and the "top K" pattern that dominates interview questions.

Unlike a Binary Search Tree — where every node maintains a strict left < parent < right ordering — a heap only guarantees that the root is the smallest (or largest) element. This relaxed constraint is what makes heaps so efficient: insert and extract run in O(log n), while peeking at the top element is O(1).

In coding interviews, heap problems appear in roughly 20-25% of technical interviews — and they often combine with other patterns (graphs, sliding windows, greedy algorithms). The good news: the heap API is tiny, and once you recognize the patterns, the solutions follow naturally.

What You'll Learn

✅ Understand heap properties, types, and array-based representation
✅ Implement MinHeap and MaxHeap from scratch
✅ Master heap operations: insert, extract, heapify
✅ Build a Priority Queue using a heap
✅ Implement Heap Sort algorithm
✅ Know when to use heaps vs BSTs vs sorted arrays
✅ Recognize heap patterns in interview problems
✅ Solve 8 classic heap interview problems step-by-step

Prerequisites

Understanding of Big O Notation & Complexity Analysis
Familiarity with Problem-Solving Patterns
Completed Trees & Binary Search Trees (heaps are specialized trees)
Basic programming knowledge in TypeScript or Python

1. Heap Fundamentals

1.1 What Is a Heap?

A heap is a complete binary tree that satisfies the heap property — every parent node is ordered relative to its children. The tree is always filled level by level, left to right, with no gaps.

Two key properties make a heap a heap:

Shape property: The tree is a complete binary tree — every level is fully filled except possibly the last, which is filled from left to right.
Heap property: Every parent is smaller (min heap) or larger (max heap) than its children.

1.2 Min Heap vs Max Heap

Property	Min Heap	Max Heap
Root	Smallest element	Largest element
Parent-child rule	Parent ≤ Children	Parent ≥ Children
Peek min	O(1)	O(n)
Peek max	O(n)	O(1)
Common use	Priority queues, Dijkstra's	Heap sort, max-priority queues

Important: A heap does not guarantee order among siblings or across levels — only between parent and child. The second-smallest element could be anywhere in the second level.

1.3 Array-Based Representation

The most efficient way to store a heap is in a flat array. Because the tree is complete, there are no gaps — every index maps to exactly one node.

For a node at index i (0-based):

Relationship	Formula
Parent	`Math.floor((i - 1) / 2)`
Left child	`2 * i + 1`
Right child	`2 * i + 2`

Array:   [1, 3, 2, 7, 6, 4, 5]
Index:    0  1  2  3  4  5  6
 
Tree mapping:
         1 (i=0)
        / \
      3     2
    (i=1)  (i=2)
    / \    / \
   7   6  4   5
 (3) (4) (5) (6)

Why arrays?

No pointer overhead (no left/right references)
Cache-friendly — contiguous memory
Index arithmetic is O(1)

1.4 Real-World Applications

Application	Heap Type	Why
Dijkstra's algorithm	Min heap	Always expand the cheapest unvisited node
Task scheduler	Min/Max heap	Execute highest-priority task first
Event-driven simulation	Min heap	Process earliest event first
Heap sort	Max heap	In-place O(n log n) sort
Median maintenance	Two heaps	Track running median efficiently
Merge K sorted lists	Min heap	Always pick the smallest head across all lists
Top-K elements	Min heap (size K)	Maintain K largest elements seen so far
Huffman coding	Min heap	Build optimal prefix codes

2. Heap Operations

Every heap supports three core operations: insert, extract, and heapify. All three rely on two helper procedures — siftUp and siftDown.

2.1 Sift Up (Bubble Up)

After inserting a new element at the end of the array, it may violate the heap property. Sift up swaps the element with its parent repeatedly until the property is restored.

Steps:

Start at the newly inserted element
Compare with parent
If out of order, swap with parent
Repeat until the element reaches its correct position or the root

Time: O(log n) — at most the height of the tree.

2.2 Sift Down (Bubble Down)

After extracting the root (and replacing it with the last element), the new root may violate the heap property. Sift down swaps the element with its smaller child (min heap) or larger child (max heap) repeatedly.

Steps:

Start at the root
Compare with both children
If out of order, swap with the smaller/larger child
Repeat until the element reaches its correct position or a leaf

Time: O(log n) — at most the height of the tree.

2.3 Insert

Add element to the end of the array (maintains shape property)
Sift up to restore heap property

Insert 0 into min heap [1, 3, 2, 7, 6, 4, 5]:
 
Step 1: Add to end → [1, 3, 2, 7, 6, 4, 5, 0]
Step 2: Sift up 0
  - 0 < 7 (parent)? Yes → swap → [1, 3, 2, 0, 6, 4, 5, 7]
  - 0 < 3 (parent)? Yes → swap → [1, 0, 2, 3, 6, 4, 5, 7]
  - 0 < 1 (parent)? Yes → swap → [0, 1, 2, 3, 6, 4, 5, 7]
  - At root → done

2.4 Extract Min/Max

Save the root (min or max element)
Move the last element to the root
Sift down to restore heap property
Return the saved element

Extract min from [1, 3, 2, 7, 6, 4, 5]:
 
Step 1: Save 1, move last to root → [5, 3, 2, 7, 6, 4]
Step 2: Sift down 5
  - Children: 3, 2. Smaller child: 2 → 5 > 2? Yes → swap → [2, 3, 5, 7, 6, 4]
  - Children: 4. Smaller child: 4 → 5 > 4? Yes → swap → [2, 3, 4, 7, 6, 5]
  - No children → done
Result: 1

2.5 Build Heap (Heapify)

Given an unsorted array, build a valid heap in-place.

Naive approach: Insert elements one by one → O(n log n).

Optimal approach (Floyd's algorithm): Start from the last non-leaf node and sift down each node. This runs in O(n) — not O(n log n) — because most nodes are near the bottom and sift very little.

Why O(n)? Roughly half the nodes are leaves (no sifting needed), a quarter sift at most 1 level, an eighth sift at most 2 levels, and so on. The sum converges to O(n).

2.6 Complexity Summary

Operation	Time	Space
Insert	O(log n)	O(1)
Extract Min/Max	O(log n)	O(1)
Peek Min/Max	O(1)	O(1)
Build Heap	O(n)	O(1)
Search	O(n)	O(1)
Delete arbitrary	O(n) for search + O(log n) for removal	O(1)

3. Implementation: MinHeap

3.1 TypeScript Implementation

// TypeScript - MinHeap Implementation
class MinHeap {
  private heap: number[] = [];
 
  get size(): number {
    return this.heap.length;
  }
 
  peek(): number | undefined {
    return this.heap[0];
  }
 
  insert(val: number): void {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }
 
  extractMin(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
 
    const min = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.siftDown(0);
    return min;
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i] >= this.heap[parent]) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
 
  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
 
      if (left < n && this.heap[left] < this.heap[smallest]) {
        smallest = left;
      }
      if (right < n && this.heap[right] < this.heap[smallest]) {
        smallest = right;
      }
      if (smallest === i) break;
 
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
 
  // Build heap from array in O(n)
  static fromArray(arr: number[]): MinHeap {
    const heap = new MinHeap();
    heap.heap = [...arr];
    // Start from last non-leaf node
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
      heap.siftDown(i);
    }
    return heap;
  }
}
 
// Usage
const heap = new MinHeap();
heap.insert(5);
heap.insert(3);
heap.insert(8);
heap.insert(1);
 
console.log(heap.peek());       // 1
console.log(heap.extractMin()); // 1
console.log(heap.extractMin()); // 3
console.log(heap.size);         // 2
 
// Build from array
const heap2 = MinHeap.fromArray([7, 3, 9, 1, 5, 2]);
console.log(heap2.extractMin()); // 1
console.log(heap2.extractMin()); // 2
console.log(heap2.extractMin()); // 3

3.2 Python Implementation

# Python - MinHeap Implementation
class MinHeap:
    def __init__(self):
        self.heap: list[int] = []
 
    @property
    def size(self) -> int:
        return len(self.heap)
 
    def peek(self) -> int | None:
        return self.heap[0] if self.heap else None
 
    def insert(self, val: int) -> None:
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)
 
    def extract_min(self) -> int | None:
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
 
        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return min_val
 
    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] >= self.heap[parent]:
                break
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
 
    def _sift_down(self, i: int) -> None:
        n = len(self.heap)
        while True:
            smallest = i
            left = 2 * i + 1
            right = 2 * i + 2
 
            if left < n and self.heap[left] < self.heap[smallest]:
                smallest = left
            if right < n and self.heap[right] < self.heap[smallest]:
                smallest = right
            if smallest == i:
                break
 
            self.heap[i], self.heap[smallest] = self.heap[smallest], self.heap[i]
            i = smallest
 
    @classmethod
    def from_array(cls, arr: list[int]) -> "MinHeap":
        heap = cls()
        heap.heap = arr[:]
        for i in range(len(arr) // 2 - 1, -1, -1):
            heap._sift_down(i)
        return heap
 
 
# Usage
heap = MinHeap()
heap.insert(5)
heap.insert(3)
heap.insert(8)
heap.insert(1)
 
print(heap.peek())        # 1
print(heap.extract_min())  # 1
print(heap.extract_min())  # 3
print(heap.size)           # 2
 
# Build from array
heap2 = MinHeap.from_array([7, 3, 9, 1, 5, 2])
print(heap2.extract_min())  # 1
print(heap2.extract_min())  # 2
print(heap2.extract_min())  # 3

4. Implementation: MaxHeap

A MaxHeap is identical to a MinHeap but with the comparison reversed — the parent must be greater than or equal to its children.

4.1 TypeScript Implementation

// TypeScript - MaxHeap Implementation
class MaxHeap {
  private heap: number[] = [];
 
  get size(): number {
    return this.heap.length;
  }
 
  peek(): number | undefined {
    return this.heap[0];
  }
 
  insert(val: number): void {
    this.heap.push(val);
    this.siftUp(this.heap.length - 1);
  }
 
  extractMax(): number | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop();
 
    const max = this.heap[0];
    this.heap[0] = this.heap.pop()!;
    this.siftDown(0);
    return max;
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i] <= this.heap[parent]) break;  // Reversed comparison
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
 
  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let largest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
 
      if (left < n && this.heap[left] > this.heap[largest]) {
        largest = left;
      }
      if (right < n && this.heap[right] > this.heap[largest]) {
        largest = right;
      }
      if (largest === i) break;
 
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      i = largest;
    }
  }
}
 
// Usage
const maxHeap = new MaxHeap();
maxHeap.insert(5);
maxHeap.insert(3);
maxHeap.insert(8);
maxHeap.insert(1);
 
console.log(maxHeap.peek());       // 8
console.log(maxHeap.extractMax()); // 8
console.log(maxHeap.extractMax()); // 5

4.2 Python Implementation

# Python - MaxHeap Implementation
class MaxHeap:
    def __init__(self):
        self.heap: list[int] = []
 
    @property
    def size(self) -> int:
        return len(self.heap)
 
    def peek(self) -> int | None:
        return self.heap[0] if self.heap else None
 
    def insert(self, val: int) -> None:
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)
 
    def extract_max(self) -> int | None:
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
 
        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return max_val
 
    def _sift_up(self, i: int) -> None:
        while i > 0:
            parent = (i - 1) // 2
            if self.heap[i] <= self.heap[parent]:  # Reversed comparison
                break
            self.heap[i], self.heap[parent] = self.heap[parent], self.heap[i]
            i = parent
 
    def _sift_down(self, i: int) -> None:
        n = len(self.heap)
        while True:
            largest = i
            left = 2 * i + 1
            right = 2 * i + 2
 
            if left < n and self.heap[left] > self.heap[largest]:
                largest = left
            if right < n and self.heap[right] > self.heap[largest]:
                largest = right
            if largest == i:
                break
 
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            i = largest
 
 
# Usage
max_heap = MaxHeap()
max_heap.insert(5)
max_heap.insert(3)
max_heap.insert(8)
max_heap.insert(1)
 
print(max_heap.peek())         # 8
print(max_heap.extract_max())  # 8
print(max_heap.extract_max())  # 5

Pro tip: In Python, you can simulate a max heap using the built-in heapq module by negating values:

# Python - Max heap using heapq (negate trick)
import heapq
 
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -8)
 
print(-heapq.heappop(max_heap))  # 8 (largest)
print(-heapq.heappop(max_heap))  # 5

5. Priority Queue

A priority queue is an abstract data type where each element has a priority, and elements are dequeued in priority order — not FIFO like a regular queue.

A heap is the standard implementation of a priority queue because it provides O(log n) insert and O(log n) extract while maintaining priority ordering.

5.1 TypeScript Implementation

// TypeScript - Priority Queue (Min Priority = highest priority)
interface PQItem<T> {
  value: T;
  priority: number;
}
 
class PriorityQueue<T> {
  private heap: PQItem<T>[] = [];
 
  get size(): number {
    return this.heap.length;
  }
 
  isEmpty(): boolean {
    return this.heap.length === 0;
  }
 
  enqueue(value: T, priority: number): void {
    this.heap.push({ value, priority });
    this.siftUp(this.heap.length - 1);
  }
 
  dequeue(): T | undefined {
    if (this.heap.length === 0) return undefined;
    if (this.heap.length === 1) return this.heap.pop()!.value;
 
    const top = this.heap[0].value;
    this.heap[0] = this.heap.pop()!;
    this.siftDown(0);
    return top;
  }
 
  peek(): T | undefined {
    return this.heap[0]?.value;
  }
 
  private siftUp(i: number): void {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[i].priority >= this.heap[parent].priority) break;
      [this.heap[i], this.heap[parent]] = [this.heap[parent], this.heap[i]];
      i = parent;
    }
  }
 
  private siftDown(i: number): void {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;
 
      if (left < n && this.heap[left].priority < this.heap[smallest].priority) {
        smallest = left;
      }
      if (right < n && this.heap[right].priority < this.heap[smallest].priority) {
        smallest = right;
      }
      if (smallest === i) break;
 
      [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
      i = smallest;
    }
  }
}
 
// Usage
const pq = new PriorityQueue<string>();
pq.enqueue("low priority task", 10);
pq.enqueue("critical bug", 1);
pq.enqueue("medium task", 5);
 
console.log(pq.dequeue()); // "critical bug" (priority 1)
console.log(pq.dequeue()); // "medium task" (priority 5)
console.log(pq.dequeue()); // "low priority task" (priority 10)

5.2 Python Implementation

# Python - Priority Queue using heapq
import heapq
from dataclasses import dataclass, field
from typing import Any
 
@dataclass(order=True)
class PQItem:
    priority: int
    value: Any = field(compare=False)
 
class PriorityQueue:
    def __init__(self):
        self.heap: list[PQItem] = []
 
    @property
    def size(self) -> int:
        return len(self.heap)
 
    def is_empty(self) -> bool:
        return len(self.heap) == 0
 
    def enqueue(self, value: Any, priority: int) -> None:
        heapq.heappush(self.heap, PQItem(priority, value))
 
    def dequeue(self) -> Any | None:
        if not self.heap:
            return None
        return heapq.heappop(self.heap).value
 
    def peek(self) -> Any | None:
        return self.heap[0].value if self.heap else None
 
 
# Usage
pq = PriorityQueue()
pq.enqueue("low priority task", 10)
pq.enqueue("critical bug", 1)
pq.enqueue("medium task", 5)
 
print(pq.dequeue())  # "critical bug" (priority 1)
print(pq.dequeue())  # "medium task" (priority 5)
print(pq.dequeue())  # "low priority task" (priority 10)

5.3 Queue vs Priority Queue

Feature	Queue (FIFO)	Priority Queue
Order	First In, First Out	Highest priority first
Enqueue	O(1)	O(log n)
Dequeue	O(1)	O(log n)
Use case	BFS, task scheduling (fair)	Dijkstra's, task scheduling (priority)
Implementation	Array / Linked list	Heap

6. Python's heapq Module

Python provides a built-in min heap via the heapq module. It operates directly on a regular list — no special class needed.

# Python - heapq module essentials
import heapq
 
# Create a heap from a list (in-place, O(n))
nums = [7, 3, 9, 1, 5, 2]
heapq.heapify(nums)
print(nums)  # [1, 3, 2, 7, 5, 9] — valid min heap
 
# Push and pop
heapq.heappush(nums, 0)
print(heapq.heappop(nums))  # 0
 
# Push and pop in one step (more efficient)
result = heapq.heapreplace(nums, 10)  # Pop smallest, then push 10
print(result)  # 1
 
# Get K smallest / largest
data = [7, 3, 9, 1, 5, 2, 8, 4, 6]
print(heapq.nsmallest(3, data))  # [1, 2, 3]
print(heapq.nlargest(3, data))   # [9, 8, 7]
 
# Heap with tuples (sorted by first element)
tasks = []
heapq.heappush(tasks, (2, "medium task"))
heapq.heappush(tasks, (1, "urgent task"))
heapq.heappush(tasks, (3, "low task"))
 
print(heapq.heappop(tasks))  # (1, "urgent task")

Key functions:

Function	Description	Time
`heapify(list)`	Convert list to heap in-place	O(n)
`heappush(heap, item)`	Push item onto heap	O(log n)
`heappop(heap)`	Pop smallest item	O(log n)
`heapreplace(heap, item)`	Pop then push (efficient)	O(log n)
`heappushpop(heap, item)`	Push then pop (efficient)	O(log n)
`nsmallest(k, iterable)`	Return K smallest elements	O(n log k)
`nlargest(k, iterable)`	Return K largest elements	O(n log k)

Note: JavaScript / TypeScript has no built-in heap. You must implement your own or use a library.

7. Heap Sort

Heap sort uses a max heap to sort an array in-place with O(n log n) time and O(1) extra space.

Algorithm:

Build a max heap from the array — O(n)
Repeatedly extract the max and place it at the end — O(n log n)
- Swap root (max) with last element
- Reduce heap size by 1
- Sift down the new root

7.1 TypeScript Implementation

// TypeScript - Heap Sort
function heapSort(arr: number[]): number[] {
  const n = arr.length;
 
  // Build max heap - start from last non-leaf
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    siftDown(arr, n, i);
  }
 
  // Extract elements one by one
  for (let end = n - 1; end > 0; end--) {
    // Move current root (max) to end
    [arr[0], arr[end]] = [arr[end], arr[0]];
    // Sift down on the reduced heap
    siftDown(arr, end, 0);
  }
 
  return arr;
}
 
function siftDown(arr: number[], heapSize: number, i: number): void {
  while (true) {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
 
    if (left < heapSize && arr[left] > arr[largest]) largest = left;
    if (right < heapSize && arr[right] > arr[largest]) largest = right;
    if (largest === i) break;
 
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    i = largest;
  }
}
 
// Usage
console.log(heapSort([7, 3, 9, 1, 5, 2, 8, 4, 6]));
// [1, 2, 3, 4, 5, 6, 7, 8, 9]

7.2 Python Implementation

# Python - Heap Sort
def heap_sort(arr: list[int]) -> list[int]:
    n = len(arr)
 
    # Build max heap
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)
 
    # Extract elements one by one
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, end, 0)
 
    return arr
 
 
def sift_down(arr: list[int], heap_size: int, i: int) -> None:
    while True:
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2
 
        if left < heap_size and arr[left] > arr[largest]:
            largest = left
        if right < heap_size and arr[right] > arr[largest]:
            largest = right
        if largest == i:
            break
 
        arr[i], arr[largest] = arr[largest], arr[i]
        i = largest
 
 
# Usage
print(heap_sort([7, 3, 9, 1, 5, 2, 8, 4, 6]))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

7.3 Heap Sort Properties

Property	Value
Time (all cases)	O(n log n)
Space	O(1) — in-place
Stable?	No
Adaptive?	No (always O(n log n))

Heap sort vs other O(n log n) sorts:

vs Quick Sort: Heap sort has guaranteed O(n log n) worst case (quick sort is O(n²) worst case), but quick sort is typically faster in practice due to cache locality
vs Merge Sort: Heap sort is in-place (O(1) space) while merge sort requires O(n) space, but merge sort is stable

8. Heaps vs Other Data Structures

Operation	Heap	BST (balanced)	Sorted Array
Find min	O(1)	O(log n)	O(1)
Find max	O(1) — max heap	O(log n)	O(1)
Insert	O(log n)	O(log n)	O(n)
Extract min/max	O(log n)	O(log n)	O(1) or O(n)
Search	O(n)	O(log n)	O(log n)
Build from array	O(n)	O(n log n)	O(n log n)
Space	O(n)	O(n) + pointers	O(n)

When to use each:

Heap: When you only need the min or max — not both, not arbitrary search
BST: When you need ordered operations (predecessor, successor, range queries)
Sorted Array: When data is static and you only need lookups

9. Classic Interview Problems

Problem 1: Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element. Note that it is the kth largest in sorted order, not the kth distinct element.

Approach: Maintain a min heap of size K. The root is always the Kth largest.

// TypeScript - Kth Largest Element
function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap();
 
  for (const num of nums) {
    heap.insert(num);
    if (heap.size > k) {
      heap.extractMin();
    }
  }
 
  return heap.peek()!;
}
 
// Usage
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

# Python - Kth Largest Element
import heapq
 
def find_kth_largest(nums: list[int], k: int) -> int:
    heap = []
    for num in nums:
        heapq.heappush(heap, num)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]
 
# Alternative one-liner
def find_kth_largest_v2(nums: list[int], k: int) -> int:
    return heapq.nlargest(k, nums)[-1]
 
print(find_kth_largest([3, 2, 1, 5, 6, 4], 2))  # 5
print(find_kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4))  # 4

Time: O(n log k). Space: O(k).

Problem 2: Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements.

Approach: Count frequencies, then use a min heap of size K to track the top K frequent elements.

// TypeScript - Top K Frequent Elements
function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
 
  // Min heap of [frequency, number]
  const heap: [number, number][] = [];
 
  const siftUp = (i: number) => {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (heap[i][0] >= heap[parent][0]) break;
      [heap[i], heap[parent]] = [heap[parent], heap[i]];
      i = parent;
    }
  };
 
  const siftDown = (i: number) => {
    while (true) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] < heap[smallest][0]) smallest = l;
      if (r < heap.length && heap[r][0] < heap[smallest][0]) smallest = r;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
  };
 
  for (const [num, count] of freq) {
    heap.push([count, num]);
    siftUp(heap.length - 1);
    if (heap.length > k) {
      heap[0] = heap.pop()!;
      siftDown(0);
    }
  }
 
  return heap.map(([_, num]) => num);
}
 
console.log(topKFrequent([1, 1, 1, 2, 2, 3], 2)); // [2, 1] or [1, 2]

# Python - Top K Frequent Elements
import heapq
from collections import Counter
 
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    # nlargest returns k items with highest counts
    return heapq.nlargest(k, freq.keys(), key=freq.get)
 
# Alternative: min heap of size k
def top_k_frequent_v2(nums: list[int], k: int) -> list[int]:
    freq = Counter(nums)
    heap = []
    for num, count in freq.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)
    return [num for count, num in heap]
 
print(top_k_frequent([1, 1, 1, 2, 2, 3], 2))  # [1, 2]

Time: O(n log k). Space: O(n) for frequency map.

Problem 3: Merge K Sorted Lists

You are given an array of k linked lists, each sorted in ascending order. Merge all lists into one sorted list.

Approach: Use a min heap to always pick the smallest element across all list heads.

// TypeScript - Merge K Sorted Lists
class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}
 
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  // Min heap storing [value, listIndex]
  const heap: [number, number][] = [];
 
  const siftUp = (i: number) => {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i][0] >= heap[p][0]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
 
  const siftDown = (i: number) => {
    while (true) {
      let s = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] < heap[s][0]) s = l;
      if (r < heap.length && heap[r][0] < heap[s][0]) s = r;
      if (s === i) break;
      [heap[i], heap[s]] = [heap[s], heap[i]];
      i = s;
    }
  };
 
  const push = (item: [number, number]) => {
    heap.push(item);
    siftUp(heap.length - 1);
  };
 
  const pop = (): [number, number] => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    heap[0] = heap.pop()!;
    siftDown(0);
    return top;
  };
 
  // Initialize heap with head of each list
  const heads = [...lists];
  for (let i = 0; i < heads.length; i++) {
    if (heads[i]) push([heads[i]!.val, i]);
  }
 
  const dummy = new ListNode();
  let current = dummy;
 
  while (heap.length > 0) {
    const [val, idx] = pop();
    current.next = new ListNode(val);
    current = current.next;
 
    heads[idx] = heads[idx]!.next;
    if (heads[idx]) push([heads[idx]!.val, idx]);
  }
 
  return dummy.next;
}

# Python - Merge K Sorted Lists
import heapq
from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    heap = []
    # Use index as tiebreaker (ListNode is not comparable)
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
 
    dummy = ListNode()
    current = dummy
 
    while heap:
        val, idx, node = heapq.heappop(heap)
        current.next = ListNode(val)
        current = current.next
 
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))
 
    return dummy.next

Time: O(N log k) where N = total nodes across all lists. Space: O(k).

Problem 4: Find Median from Data Stream

Design a data structure that supports adding numbers and finding the median efficiently.

Approach: Use two heaps — a max heap for the lower half and a min heap for the upper half. The median is always at the top of one or both heaps.

Invariants:

Max heap stores the smaller half, min heap stores the larger half
Max heap size equals min heap size (even total) or is one larger (odd total)
Every element in max heap ≤ every element in min heap

// TypeScript - Median Finder with Two Heaps
class MedianFinder {
  private lo: MaxHeap; // max heap — lower half
  private hi: MinHeap; // min heap — upper half
 
  constructor() {
    this.lo = new MaxHeap();
    this.hi = new MinHeap();
  }
 
  addNum(num: number): void {
    // Always add to max heap first
    this.lo.insert(num);
 
    // Ensure max of lower ≤ min of upper
    if (this.hi.size > 0 && this.lo.peek()! > this.hi.peek()!) {
      this.hi.insert(this.lo.extractMax()!);
    }
 
    // Balance sizes: lo can be at most 1 larger
    if (this.lo.size > this.hi.size + 1) {
      this.hi.insert(this.lo.extractMax()!);
    } else if (this.hi.size > this.lo.size) {
      this.lo.insert(this.hi.extractMin()!);
    }
  }
 
  findMedian(): number {
    if (this.lo.size > this.hi.size) {
      return this.lo.peek()!;
    }
    return (this.lo.peek()! + this.hi.peek()!) / 2;
  }
}
 
// Usage
const mf = new MedianFinder();
mf.addNum(1);
mf.addNum(2);
console.log(mf.findMedian()); // 1.5
mf.addNum(3);
console.log(mf.findMedian()); // 2

# Python - Median Finder with Two Heaps
import heapq
 
class MedianFinder:
    def __init__(self):
        self.lo: list[int] = []  # max heap (negate values)
        self.hi: list[int] = []  # min heap
 
    def add_num(self, num: int) -> None:
        heapq.heappush(self.lo, -num)
 
        # Ensure max of lower ≤ min of upper
        if self.hi and -self.lo[0] > self.hi[0]:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
 
        # Balance sizes
        if len(self.lo) > len(self.hi) + 1:
            heapq.heappush(self.hi, -heapq.heappop(self.lo))
        elif len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
 
    def find_median(self) -> float:
        if len(self.lo) > len(self.hi):
            return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2
 
 
# Usage
mf = MedianFinder()
mf.add_num(1)
mf.add_num(2)
print(mf.find_median())  # 1.5
mf.add_num(3)
print(mf.find_median())  # 2.0

Time: O(log n) per add, O(1) for find median. Space: O(n).

Problem 5: K Closest Points to Origin

Given an array of points where points[i] = [xi, yi], return the k closest points to the origin (0, 0).

Approach: Use a max heap of size K. If a point is closer than the farthest point in the heap, replace it.

// TypeScript - K Closest Points to Origin
function kClosest(points: number[][], k: number): number[][] {
  // Max heap by distance (negate for max behavior using min heap logic)
  const heap: [number, number[]][] = []; // [negDist, point]
 
  const siftUp = (i: number) => {
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i][0] <= heap[p][0]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
 
  const siftDown = (i: number) => {
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] > heap[largest][0]) largest = l;
      if (r < heap.length && heap[r][0] > heap[largest][0]) largest = r;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
  };
 
  for (const point of points) {
    const dist = point[0] ** 2 + point[1] ** 2;
    heap.push([dist, point]);
    siftUp(heap.length - 1);
    if (heap.length > k) {
      heap[0] = heap.pop()!;
      siftDown(0);
    }
  }
 
  return heap.map(([_, point]) => point);
}
 
console.log(kClosest([[1, 3], [-2, 2]], 1)); // [[-2, 2]]

# Python - K Closest Points to Origin
import heapq
 
def k_closest(points: list[list[int]], k: int) -> list[list[int]]:
    # Max heap of size k (negate distance)
    heap = []
    for x, y in points:
        dist = -(x * x + y * y)  # negate for max heap
        heapq.heappush(heap, (dist, [x, y]))
        if len(heap) > k:
            heapq.heappop(heap)
    return [point for _, point in heap]
 
print(k_closest([[1, 3], [-2, 2]], 1))  # [[-2, 2]]

Time: O(n log k). Space: O(k).

Problem 6: Task Scheduler

Given tasks represented by characters and a cooldown period n, find the minimum number of intervals the CPU needs to finish all tasks.

Approach: Use a max heap to always execute the most frequent remaining task. After executing, place the task in a cooldown queue.

// TypeScript - Task Scheduler
function leastInterval(tasks: string[], n: number): number {
  const freq = new Map<string, number>();
  for (const task of tasks) {
    freq.set(task, (freq.get(task) || 0) + 1);
  }
 
  // Max heap of frequencies
  const heap: number[] = [];
  const pushHeap = (val: number) => {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i] <= heap[p]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const popHeap = (): number => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    heap[0] = heap.pop()!;
    let i = 0;
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l] > heap[largest]) largest = l;
      if (r < heap.length && heap[r] > heap[largest]) largest = r;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
    return top;
  };
 
  for (const count of freq.values()) {
    pushHeap(count);
  }
 
  const cooldown: [number, number][] = []; // [count, availableTime]
  let time = 0;
 
  while (heap.length > 0 || cooldown.length > 0) {
    time++;
 
    if (heap.length > 0) {
      const count = popHeap() - 1;
      if (count > 0) {
        cooldown.push([count, time + n]);
      }
    }
 
    if (cooldown.length > 0 && cooldown[0][1] === time) {
      pushHeap(cooldown.shift()![0]);
    }
  }
 
  return time;
}
 
console.log(leastInterval(["A","A","A","B","B","B"], 2)); // 8

# Python - Task Scheduler
import heapq
from collections import Counter, deque
 
def least_interval(tasks: list[str], n: int) -> int:
    freq = Counter(tasks)
    # Max heap (negate for max behavior)
    heap = [-count for count in freq.values()]
    heapq.heapify(heap)
 
    cooldown = deque()  # (count, available_time)
    time = 0
 
    while heap or cooldown:
        time += 1
 
        if heap:
            count = heapq.heappop(heap) + 1  # +1 because negated
            if count < 0:
                cooldown.append((count, time + n))
 
        if cooldown and cooldown[0][1] == time:
            heapq.heappush(heap, cooldown.popleft()[0])
 
    return time
 
print(least_interval(["A","A","A","B","B","B"], 2))  # 8

Time: O(n × m) where m = cooldown period. Space: O(26) = O(1) for task frequencies.

Problem 7: Reorganize String

Given a string s, rearrange the characters so that no two adjacent characters are the same. Return any valid result, or "" if impossible.

Approach: Use a max heap to always place the most frequent character next, alternating with the previous character.

// TypeScript - Reorganize String
function reorganizeString(s: string): string {
  const freq = new Map<string, number>();
  for (const c of s) {
    freq.set(c, (freq.get(c) || 0) + 1);
  }
 
  // Max heap of [count, char]
  const heap: [number, string][] = [];
  const push = (item: [number, string]) => {
    heap.push(item);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i][0] <= heap[p][0]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const pop = (): [number, string] => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    heap[0] = heap.pop()!;
    let i = 0;
    while (true) {
      let largest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l][0] > heap[largest][0]) largest = l;
      if (r < heap.length && heap[r][0] > heap[largest][0]) largest = r;
      if (largest === i) break;
      [heap[i], heap[largest]] = [heap[largest], heap[i]];
      i = largest;
    }
    return top;
  };
 
  for (const [char, count] of freq) {
    push([count, char]);
  }
 
  let result = "";
  let prev: [number, string] | null = null;
 
  while (heap.length > 0) {
    const [count, char] = pop();
    result += char;
 
    if (prev && prev[0] > 0) {
      push(prev);
    }
 
    prev = [count - 1, char];
  }
 
  return result.length === s.length ? result : "";
}
 
console.log(reorganizeString("aab"));   // "aba"
console.log(reorganizeString("aaab"));  // ""

# Python - Reorganize String
import heapq
from collections import Counter
 
def reorganize_string(s: str) -> str:
    freq = Counter(s)
    # Max heap (negate counts)
    heap = [(-count, char) for char, count in freq.items()]
    heapq.heapify(heap)
 
    result = []
    prev = None  # (neg_count, char)
 
    while heap:
        neg_count, char = heapq.heappop(heap)
        result.append(char)
 
        if prev and prev[0] < 0:
            heapq.heappush(heap, prev)
 
        prev = (neg_count + 1, char)  # +1 because negated
 
    return "".join(result) if len(result) == len(s) else ""
 
print(reorganize_string("aab"))   # "aba"
print(reorganize_string("aaab"))  # ""

Time: O(n log k) where k = unique characters. Space: O(k).

Problem 8: Meeting Rooms II

Given an array of meeting time intervals [start, end], find the minimum number of conference rooms required.

Approach: Sort by start time. Use a min heap to track end times of ongoing meetings. If the earliest ending meeting finishes before the next one starts, reuse that room.

// TypeScript - Meeting Rooms II
function minMeetingRooms(intervals: number[][]): number {
  intervals.sort((a, b) => a[0] - b[0]);
 
  // Min heap of end times
  const heap: number[] = [];
  const push = (val: number) => {
    heap.push(val);
    let i = heap.length - 1;
    while (i > 0) {
      const p = Math.floor((i - 1) / 2);
      if (heap[i] >= heap[p]) break;
      [heap[i], heap[p]] = [heap[p], heap[i]];
      i = p;
    }
  };
  const pop = (): number => {
    const top = heap[0];
    if (heap.length === 1) { heap.pop(); return top; }
    heap[0] = heap.pop()!;
    let i = 0;
    while (true) {
      let smallest = i;
      const l = 2 * i + 1, r = 2 * i + 2;
      if (l < heap.length && heap[l] < heap[smallest]) smallest = l;
      if (r < heap.length && heap[r] < heap[smallest]) smallest = r;
      if (smallest === i) break;
      [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
      i = smallest;
    }
    return top;
  };
 
  for (const [start, end] of intervals) {
    // If earliest ending room is free, reuse it
    if (heap.length > 0 && heap[0] <= start) {
      pop();
    }
    push(end);
  }
 
  return heap.length;
}
 
console.log(minMeetingRooms([[0,30],[5,10],[15,20]])); // 2
console.log(minMeetingRooms([[7,10],[2,4]]));           // 1

# Python - Meeting Rooms II
import heapq
 
def min_meeting_rooms(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    heap = []  # min heap of end times
 
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)
 
    return len(heap)
 
print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms([[7,10],[2,4]]))            # 1

Time: O(n log n). Space: O(n).

10. Pattern Recognition Guide

Signal in the Problem	Pattern	Data Structure
"K largest" / "K smallest"	Top-K	Min heap of size K
"K most frequent"	Top-K + frequency	Count + min heap of size K
"Median" / "middle element"	Two heaps	Max heap (lower) + min heap (upper)
"Merge K sorted"	K-way merge	Min heap of size K
"Schedule" / "cooldown" / "interval"	Greedy + heap	Max heap of frequencies
"Closest" / "nearest"	Top-K by distance	Max heap of size K (or min heap)
"Continuously add + query min/max"	Streaming	Min or max heap
"Reorganize" / "no adjacent same"	Greedy interleave	Max heap of frequencies

Decision Flowchart

Interview Heuristics

"K largest" → Min heap of size K (counterintuitive but correct — the root is the Kth largest)
"K smallest" → Max heap of size K
"Median from stream" → Two heaps: max heap (lower half) + min heap (upper half)
"Merge K sorted X" → Min heap holding one element from each source
"Rearrange with constraints" → Max heap of frequencies + greedy placement
"Most frequent + cooldown" → Max heap + queue for cooldown tracking

11. Complexity Reference

Heap Operations

Operation	Min Heap	Max Heap
Peek	O(1)	O(1)
Insert	O(log n)	O(log n)
Extract	O(log n)	O(log n)
Build	O(n)	O(n)
Search	O(n)	O(n)

Problem Complexities

Problem	Time	Space
Kth Largest Element	O(n log k)	O(k)
Top K Frequent	O(n log k)	O(n)
Merge K Sorted Lists	O(N log k)	O(k)
Find Median (stream)	O(log n) per add	O(n)
K Closest Points	O(n log k)	O(k)
Task Scheduler	O(n)	O(1)
Reorganize String	O(n log k)	O(k)
Meeting Rooms II	O(n log n)	O(n)

12. Practice Problems

Easy (Build Foundation)

#	Problem	Pattern	Approach
1	Last Stone Weight	Max heap	Smash two heaviest stones repeatedly
2	Kth Largest Element in a Stream	Min heap size K	Maintain K elements, root is answer
3	Relative Ranks	Max heap	Extract by rank order
4	Sort Array by Increasing Frequency	Heap + frequency	Count then heap sort by frequency

Medium (Build Confidence)

#	Problem	Pattern	Approach
5	Kth Largest Element in an Array	Top-K	Min heap of size K
6	Top K Frequent Elements	Top-K + counting	Count + min heap size K
7	K Closest Points to Origin	Top-K by distance	Max heap of size K
8	Task Scheduler	Greedy + heap	Max heap + cooldown queue
9	Reorganize String	Greedy interleave	Max heap of frequencies
10	Sort Characters By Frequency	Heap + frequency	Max heap of (count, char)
11	Meeting Rooms II	Sweep line + heap	Min heap of end times
12	Ugly Number II	Min heap + dedup	Generate candidates via heap

Hard (Master Level)

#	Problem	Pattern	Approach
13	Find Median from Data Stream	Two heaps	Max heap (lower) + min heap (upper)
14	Merge K Sorted Lists	K-way merge	Min heap of K heads
15	Sliding Window Median	Two heaps + window	Lazy deletion with two heaps
16	IPO	Two heaps (greedy)	Sort by capital, max heap for profit
17	Smallest Range Covering Elements from K Lists	K-way merge + window	Min heap tracking all K lists

Summary

Heaps are deceptively simple — a single rule (parent ≤ children) gives you O(1) access to the minimum element with O(log n) updates.

The core operations:

Insert: Add to end, sift up — O(log n)
Extract: Remove root, sift down — O(log n)
Build heap: Floyd's algorithm — O(n)
Peek: Just read the root — O(1)

The key patterns:

Top-K → Min heap of size K (for K largest) or max heap of size K (for K smallest)
Two heaps → Median finding, data stream problems
K-way merge → Min heap holding one element per source
Greedy + heap → Task scheduling, string reorganization
Interval problems → Min heap of end times

Python advantage: The heapq module gives you a production-ready min heap. For max heap, negate your values. JavaScript/TypeScript developers: you'll need to implement your own or use a library.

What's next in the DSA series? The next post covers Dynamic Programming & Greedy Algorithms — the algorithmic paradigms that solve optimization problems by breaking them into overlapping subproblems (DP) or making locally optimal choices (greedy). You'll learn memoization, tabulation, and classic patterns like knapsack, longest subsequence, and coin change.

Previous: Graphs & Graph Algorithms
Series Overview: Data Structures & Algorithms Roadmap