Heap & Priority Queue Explained

What is a Heap?

A heap is a specialized tree-based data structure that satisfies two key properties:

• Complete Binary Tree: Every level is fully filled except possibly the last, which is filled from left to right
• Heap Property: The value of each node is ordered relative to its children (either always greater or always smaller)

Because a heap is a complete binary tree, it can be efficiently stored in an array. For a node at index i:

• Parent is at index Math.floor((i - 1) / 2)
• Left child is at index 2 * i + 1
• Right child is at index 2 * i + 2

Min Heap vs Max Heap

The heap property determines whether you have a min heap or max heap:

• Min Heap: Parent is always smaller than or equal to children. The smallest element is at the root.
• Max Heap: Parent is always greater than or equal to children. The largest element is at the root.

       Min Heap                    Max Heap
          1                           9
        /   \                       /   \
       3     2                     7     8
      / \   / \                   / \   / \
     7   6 5   4                 3   6 2   5

// Root is always the minimum     // Root is always the maximum

When to Use a Heap

Recognize these problem patterns that signal a heap solution:

• Top K / Kth Largest/Smallest: Find the K largest elements, Kth largest element, K closest points
• Streaming Data: Find median in a data stream, sliding window maximum
• Merge K Sorted: Merge K sorted lists, K sorted arrays, or K-way merge
• Scheduling: Task scheduling, meeting rooms, CPU interval problems
• Graph Algorithms: Dijkstra's shortest path, Prim's minimum spanning tree

Heap Operations & Time Complexity

Why is heapify O(n)? While it might seem like O(n log n) since we bubble down n elements, most nodes are near the bottom of the tree where bubble down is cheap. Mathematically, the sum converges to O(n).

MinHeap Implementation in TypeScript

Let's implement a MinHeap class from scratch. Understanding the implementation helps you debug heap problems in interviews:

class MinHeap {
  private heap: number[] = []

  // Get parent/child indices
  private parent(i: number): number {
    return Math.floor((i - 1) / 2)
  }
  private leftChild(i: number): number {
    return 2 * i + 1
  }
  private rightChild(i: number): number {
    return 2 * i + 2
  }

  // Swap two elements
  private swap(i: number, j: number): void {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
  }

  // Insert: Add to end, bubble up
  insert(val: number): void {
    this.heap.push(val)
    this.bubbleUp(this.heap.length - 1)
  }

  private bubbleUp(index: number): void {
    while (index > 0) {
      const parentIdx = this.parent(index)
      if (this.heap[parentIdx] <= this.heap[index]) break
      this.swap(parentIdx, index)
      index = parentIdx
    }
  }

  // Extract min: Remove root, replace with last, bubble down
  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.bubbleDown(0)
    return min
  }

  private bubbleDown(index: number): void {
    const length = this.heap.length
    while (true) {
      let smallest = index
      const left = this.leftChild(index)
      const right = this.rightChild(index)

      if (left < length && this.heap[left] < this.heap[smallest]) {
        smallest = left
      }
      if (right < length && this.heap[right] < this.heap[smallest]) {
        smallest = right
      }
      if (smallest === index) break

      this.swap(index, smallest)
      index = smallest
    }
  }

  // Peek at minimum without removing
  peek(): number | undefined {
    return this.heap[0]
  }

  size(): number {
    return this.heap.length
  }
}

Common Problems & Solutions

Problem 1: Kth Largest Element in an Array

Question: Find the kth largest element in an unsorted array. Note that it is the kth largest in sorted order, not the kth distinct element.

Key Insight: Use a min heap of size K. After processing all elements, the root is the Kth largest.

function findKthLargest(nums: number[], k: number): number {
  const minHeap = new MinHeap()

  for (const num of nums) {
    minHeap.insert(num)

    // Keep heap size at k
    // Smallest elements get ejected, k largest remain
    if (minHeap.size() > k) {
      minHeap.extractMin()
    }
  }

  // Root is the kth largest
  return minHeap.peek()!
}

// Example: findKthLargest([3,2,1,5,6,4], 2) → 5
// After processing: heap contains [5, 6]
// The min of those (5) is the 2nd largest

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

Problem 2: Merge K Sorted Lists

Question: Merge k sorted linked lists into one sorted list.

Key Insight: Use a min heap to always get the smallest element among all list heads. This is more efficient than merging pairs repeatedly.

// Using a generic heap that can compare ListNodes
function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
  // Min heap ordered by node value
  const minHeap = new MinHeap<ListNode>((a, b) => a.val - b.val)

  // Add the head of each non-empty list
  for (const list of lists) {
    if (list) minHeap.insert(list)
  }

  const dummy = new ListNode(0)
  let current = dummy

  while (minHeap.size() > 0) {
    // Get the smallest node
    const smallest = minHeap.extractMin()!
    current.next = smallest
    current = current.next

    // If this list has more nodes, add the next one
    if (smallest.next) {
      minHeap.insert(smallest.next)
    }
  }

  return dummy.next
}

// Example: [[1,4,5],[1,3,4],[2,6]] → [1,1,2,3,4,4,5,6]

Time: O(n log k) where n is total nodes, k is number of lists | Space: O(k)

Problem 3: Find Median from Data Stream

Question: Design a data structure that supports adding numbers and finding the median of all elements added so far.

Key Insight: Use two heaps! A max heap for the smaller half and a min heap for the larger half. The median is at the top of one or both heaps.

class MedianFinder {
  private maxHeap: MaxHeap  // smaller half (max at top)
  private minHeap: MinHeap  // larger half (min at top)

  constructor() {
    this.maxHeap = new MaxHeap()
    this.minHeap = new MinHeap()
  }

  addNum(num: number): void {
    // Always add to maxHeap first
    this.maxHeap.insert(num)

    // Balance: largest of smaller half goes to larger half
    this.minHeap.insert(this.maxHeap.extractMax()!)

    // Ensure maxHeap has >= elements as minHeap
    if (this.maxHeap.size() < this.minHeap.size()) {
      this.maxHeap.insert(this.minHeap.extractMin()!)
    }
  }

  findMedian(): number {
    if (this.maxHeap.size() > this.minHeap.size()) {
      return this.maxHeap.peek()!
    }
    return (this.maxHeap.peek()! + this.minHeap.peek()!) / 2
  }
}

// Example usage:
// addNum(1) → maxHeap: [1], minHeap: []
// addNum(2) → maxHeap: [1], minHeap: [2]
// findMedian() → (1 + 2) / 2 = 1.5
// addNum(3) → maxHeap: [2,1], minHeap: [3]
// findMedian() → 2

Time: O(log n) for addNum, O(1) for findMedian | Space: O(n)

Problem 4: Top K Frequent Elements

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

Key Insight: First count frequencies with a hash map, then use a min heap of size k to keep track of the k most frequent.

function topKFrequent(nums: number[], k: number): number[] {
  // Step 1: Count frequencies
  const freqMap = new Map<number, number>()
  for (const num of nums) {
    freqMap.set(num, (freqMap.get(num) || 0) + 1)
  }

  // Step 2: Use min heap of size k
  // Heap stores [num, frequency], ordered by frequency
  const minHeap = new MinHeap<[number, number]>((a, b) => a[1] - b[1])

  for (const [num, freq] of freqMap) {
    minHeap.insert([num, freq])

    if (minHeap.size() > k) {
      minHeap.extractMin()  // Remove least frequent
    }
  }

  // Step 3: Extract results
  const result: number[] = []
  while (minHeap.size() > 0) {
    result.push(minHeap.extractMin()![0])
  }

  return result
}

// Example: topKFrequent([1,1,1,2,2,3], 2) → [1, 2]
// Frequencies: {1: 3, 2: 2, 3: 1}
// Top 2 frequent: 1 and 2

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

Pro Tips

• Know your language: Python has heapq (min heap only), Java has PriorityQueue. In interviews, you may need to implement or explain the structure.
• Min heap for K largest: Counterintuitively, use a min heap of size K to find K largest elements. The min heap "guards" the top K by ejecting smaller elements.
• Two heaps for median: When you need to track the middle of a stream, the two-heap pattern is the go-to solution.
• Heap vs sorting: If you need all elements sorted, just sort. Use heaps when you only need the top K or need to process elements as they stream in.
• Custom comparators: Many heap problems require custom comparison. Practice implementing heaps with comparator functions.

Practice Problems

Ready to test your understanding? Try these LeetCode problems:

• Easy: Last Stone Weight, Kth Largest Element in a Stream
• Medium: Kth Largest Element in an Array, Top K Frequent Elements, K Closest Points to Origin, Task Scheduler
• Hard: Merge K Sorted Lists, Find Median from Data Stream, Sliding Window Maximum, IPO

Continue Learning

• Binary Search Deep Dive - Another O(log n) technique for sorted data
• Two Pointers Pattern - Efficient array traversal techniques
• Hash Maps: When and Why - Often combined with heaps for frequency problems
• Start Practicing - Apply heaps to real interview problems