Heaps: Fundamentals, Operations & Complexity

Heaps

Why This Matters

A heap is a complete binary tree that satisfies the heap property. In a min-heap, every parent is smaller than its children. In a max-heap, every parent is larger. This structure enables efficient access to the minimum (or maximum) element.

This matters because heaps are the foundation of priority queues, which are used everywhere: task scheduling (process highest priority first), Dijkstra's algorithm (shortest path), merge k sorted lists, and finding top k elements. Heaps also enable heap sort, an efficient in-place sorting algorithm.

In interviews, heap problems test your understanding of the heap property, heap operations, and your ability to recognize when a heap is the right data structure. Many problems that seem complex become simple when you recognize they're heap problems.

What Engineers Usually Get Wrong

Most engineers think "a heap is just a sorted array." While both give you access to min/max, heaps maintain partial ordering (heap property) which is cheaper to maintain than full sorting. Engineers often use sorted arrays when heaps would be more efficient.

Engineers also confuse heaps with binary search trees. A heap is a complete binary tree with heap property (parent-child relationship), not BST property (left < node < right). Heaps don't support efficient search—they're optimized for min/max access.

Another common mistake is not understanding heapify. Building a heap from an array is O(n), not O(n log n). This is because most nodes are near the bottom, and heapify works bottom-up. Understanding this helps you optimize heap construction.

How This Breaks Systems in the Real World

A task scheduler was using a sorted array to manage task priorities. When a new high-priority task arrived, it inserted it in sorted position (O(n)). When processing tasks, it removed the highest priority task (O(1)). Under normal load, this worked. But during a traffic spike, thousands of tasks arrived per second. The O(n) insertions became a bottleneck. The service became slow.

The fix? Use a heap (priority queue). Insertion is O(log n), and extracting max is O(log n). This scales much better. The lesson? Heaps are optimized for frequent min/max operations with insertions. Sorted arrays are better for infrequent changes with frequent access.

Another story: A service was finding the top k elements from a stream. It maintained a sorted array of the top k. For each new element, it checked if it was larger than the smallest in the array, and if so, inserted it in sorted position. This was O(k) per element, or O(nk) total. The fix? Use a min-heap of size k. Insertion is O(log k), making total time O(n log k). Much better for large n.

Heap Fundamentals

Heap Properties

1. Complete Binary Tree: All levels filled except possibly the last, filled left to right
2. Heap Property:
   • Min-heap: Parent ≤ children (root is minimum)
   • Max-heap: Parent ≥ children (root is maximum)

Heap Structure

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

Array Representation

Heaps are typically stored in arrays (not pointers):

• Parent at index i: children at 2i+1 and 2i+2
• Child at index i: parent at ⌊(i-1)/2⌋
• Root at index 0

Array: [1, 3, 2, 5, 4, 7, 6]
Index:  0  1  2  3  4  5  6

Tree:
       1 (0)
      / \
   3(1)  2(2)
   / \   / \
5(3) 4(4) 7(5) 6(6)

Heap Operations

Insert (Bubble Up)

1class MinHeap {
2  private heap: number[] = [];
3
4  insert(val: number): void {
5    this.heap.push(val);
6    this.bubbleUp(this.heap.length - 1);
7  }
8
9  private bubbleUp(index: number): void {
10    while (index > 0) {
11      const parent = Math.index

Extract Min/Max (Bubble Down)

1extractMin(): number | undefined {
2  if (this.heap.length === 0) return undefined;
3  if (this.heap.length === 1) return this.heap.pop();
4
5  const min = this.heap[0];
6  this.heap[0] = this.heap.pop()!; // Move last element to root
7  this.bubbleDown

Peek (Get Min/Max)

1peek(): number | undefined {
2  return this.heap[0];
3}
4
5// Time: O(1)
6// Space: O(1)

Complete Min-Heap Implementation

1class MinHeap {
2  private heap: number[] = [];
3
4  insert(val: number): void {
5    this.heap.push(val);
6    this.bubbleUp(this.heap.length - 1);
7  }
8
9  extractMin(): number | undefined {
10    if (this.heap.length === 0) return undefined;

Heapify (Build Heap)

Building a heap from an unsorted array is O(n), not O(n log n).

Bottom-Up Heapify

1function buildHeap(arr: number[]): void {
2  // Start from last non-leaf node (parent of last element)
3  const lastParent = Math.floor((arr.length - 2) / 2);
4  
5  // Heapify from bottom to top
6  for (let i = lastParent; i >= 0; i--) {
7    heapifyDown(arr, i, arr.length);
8  }
9}
10
11function heapifyDown(arr: number[], index  heapSize

Why O(n)?

• Half the nodes are leaves (no children)
• Quarter are one level up (at most 1 swap)
• Only O(log n) levels, and most work is at bottom levels
• Mathematical analysis shows sum of swaps is O(n)

Examples

Example 1: Find K Largest Elements

1function findKLargest(nums: number[], k: number): number[] {
2  // Use min-heap of size k
3  const minHeap = new MinHeap();
4
5  for (const num of nums) {
6    if (minHeap.size() < k) {
7      minHeap.insert(num);
8    } else if (num > minHeap.peek()!) {
9      minHeap.extractMin

Example 2: Merge K Sorted Lists

1class ListNode {
2  val: number;
3  next: ListNode | null = null;
4  constructor(val: number) {
5    this.val = val;
6  }
7}
8
9function mergeKLists(lists: (ListNode | null)[]): ListNode | null {
10  // Min-heap of size k (one node from each list)
11  const heap = new MinHeap();
12  const heads: ListNode[] = [];

Example 3: Heap Sort

1function heapSort(arr: number[]): void {
2  // Build max-heap
3  buildMaxHeap(arr);
4
5  // Extract max repeatedly
6  for (let i = arr.length - 1; i > 0; i--) {
7    // Swap root (max) with last element
8    [arr[0], arr[i]] = [arr[i], arr[0]];
9    // Heapify root (ignore last element)
10    heapifyDownMax(arr, 0, i

Common Pitfalls

• Confusing heap with BST: Heaps maintain heap property (parent-child), not BST property (left < node < right)
• Not using array representation: Using pointers is less efficient. Arrays have better cache locality
• Wrong heapify direction: Build heap bottom-up (O(n)), not top-down (O(n log n))
• Index calculation errors: Parent = ⌊(i-1)/2⌋, Left = 2i+1, Right = 2i+2
• Not maintaining heap property: After insert/extract, must bubble up/down
• Using wrong heap type: Min-heap for max operations (or vice versa)
• Not handling empty heap: Always check isEmpty() before extractMin()

Failure Stories You'll Recognize

The Sorted Array Bottleneck: A task scheduler used a sorted array for priorities. Insertions were O(n). During traffic spikes, this became a bottleneck. The fix? Use a heap. Insertions are O(log n), much better for high-frequency operations.

The Wrong Data Structure: A service was finding top k elements. It used a BST, which gave O(log n) operations. But it only needed min/max, not search. The fix? Use a heap. Simpler and more efficient for min/max operations.

The O(n log n) Build: A service was building a heap by inserting elements one by one (O(n log n)). But it could build from array in O(n). The fix? Use bottom-up heapify. The lesson? Building a heap is O(n), not O(n log n).

What Interviewers Are Really Testing

They want to see you recognize when a heap is the right tool. Junior engineers use sorted arrays or BSTs. Senior engineers recognize heap problems and use heaps efficiently.

When they ask "find k largest elements," they're testing:

• Do you recognize this is a heap problem?
• Do you use min-heap of size k (not max-heap)?
• Do you understand O(n log k) vs O(n log n)?

Interview Questions

Beginner

Q: What is a heap and what are its main operations?

A:

Heap: A complete binary tree satisfying heap property:

• Min-heap: Parent ≤ children (root is minimum)
• Max-heap: Parent ≥ children (root is maximum)

Main Operations:

• Insert: Add element and bubble up - O(log n)
• Extract Min/Max: Remove root, replace with last element, bubble down - O(log n)
• Peek: Get min/max without removing - O(1)
• Build Heap: Convert array to heap - O(n)

Key Properties:

• Complete binary tree (all levels filled except last, left to right)
• Stored in array (not pointers) for efficiency
• Optimized for min/max access, not search

Use Cases: Priority queues, heap sort, finding top k elements, merge k sorted lists

Intermediate

Q: How do you build a heap from an unsorted array? What's the time complexity?

A:

Approach: Bottom-up heapify

function buildHeap(arr: number[]): void {
  // Start from last non-leaf node
  const lastParent = Math.floor((arr.length - 2) / 2);
  
  // Heapify from bottom to top
  for (let i = lastParent; i >= 0; i--) {
    heapifyDown(arr, i, arr.length);
  }
}

function heapifyDown(arr: number[], index: number, heapSize: number): void {
  while (true) {
    let smallest = index;
    const left = 2 * index + 1;
    const right = 2 * index + 2;

    if (left < heapSize && arr[left] < arr[smallest]) {
      smallest = left;
    }
    if (right < heapSize && arr[right] < arr[smallest]) {
      smallest = right;
    }

    if (smallest === index) break;
    [arr[index], arr[smallest]] = [arr[smallest], arr[index]];
    index = smallest;
  }
}

// Time: O(n) - not O(n log n)!
// Space: O(1)

Why O(n)?

• Half the nodes are leaves (no children to swap)
• Quarter are one level up (at most 1 swap)
• Only nodes near root need multiple swaps
• Mathematical sum: O(n)

Key Insight: Start from bottom (last non-leaf), work upward. Most nodes are leaves, so most work is cheap.

Senior

Q: Design a data structure to find the median of a stream of numbers efficiently. How would you implement it?

A:

Challenge: Median requires access to middle element(s). Single heap gives min/max, not median.

Solution: Use two heaps - max-heap for lower half, min-heap for upper half.

class MedianFinder {
  private maxHeap: number[] = []; // Lower half (max at root)
  private minHeap: number[] = [];  // Upper half (min at root)

  addNum(num: number): void {
    // Add to appropriate heap
    if (this.maxHeap.length === 0 || num <= this.getMax(this.maxHeap)) {
      this.insertMaxHeap(this.maxHeap, num);
    } else {
      this.insertMinHeap(this.minHeap, num);
    }

    // Balance heaps (difference at most 1)
    if (this.maxHeap.length > this.minHeap.length + 1) {
      const max = this.extractMax(this.maxHeap);
      this.insertMinHeap(this.minHeap, max);
    } else if (this.minHeap.length > this.maxHeap.length + 1) {
      const min = this.extractMin(this.minHeap);
      this.insertMaxHeap(this.maxHeap, min);
    }
  }

  findMedian(): number {
    if (this.maxHeap.length === this.minHeap.length) {
      return (this.getMax(this.maxHeap) + this.getMin(this.minHeap)) / 2;
    } else if (this.maxHeap.length > this.minHeap.length) {
      return this.getMax(this.maxHeap);
    } else {
      return this.getMin(this.minHeap);
    }
  }

  // Helper methods for max-heap and min-heap operations
  private insertMaxHeap(heap: number[], val: number): void {
    heap.push(val);
    this.bubbleUpMax(heap, heap.length - 1);
  }

  private insertMinHeap(heap: number[], val: number): void {
    heap.push(val);
    this.bubbleUpMin(heap, heap.length - 1);
  }

  // ... implement bubbleUp, extractMax, extractMin, getMax, getMin
}

// Time: addNum O(log n), findMedian O(1)
// Space: O(n)
// Edge cases: empty stream, single number, two numbers

How it works:

• Max-heap stores lower half (largest at root)
• Min-heap stores upper half (smallest at root)
• Median is max of lower half (if odd count) or average of both roots (if even)
• Balance heaps so size difference ≤ 1

• Heap: Complete binary tree with heap property (min-heap: parent ≤ children, max-heap: parent ≥ children)
• Array representation: Stored in array for efficiency. Parent = ⌊(i-1)/2⌋, Left = 2i+1, Right = 2i+2
• Operations: Insert O(log n), ExtractMin/Max O(log n), Peek O(1), BuildHeap O(n)
• Priority Queue: Heap is perfect for priority queues (process highest priority first)
• Use cases: Task scheduling, Dijkstra's algorithm, finding top k, merge k sorted lists, heap sort
• Heapify: Building heap from array is O(n) (bottom-up), not O(n log n) (top-down)
• Min-heap vs Max-heap: Choose based on whether you need minimum or maximum
• Not for search: Heaps don't support efficient search (use BST for that)
• Complete binary tree: All levels filled except last, filled left to right
• Edge cases: Empty heap, single element, duplicate values, balancing after operations

How InterviewCrafted Will Teach This

We'll teach heaps through priority queue problems, not abstract definitions. Instead of memorizing "a heap is a complete binary tree," you'll learn through scenarios like "how do you find k largest elements?" or "how do you merge k sorted lists?"

You'll see how heaps are used in real systems (task schedulers, shortest path algorithms) and understand when to choose heaps over sorted arrays or BSTs. When an interviewer asks "find k largest," you'll think "min-heap of size k"—not "sort the array."

• Trees - Heaps are complete binary trees with heap property. Understanding trees helps understand heap structure.
• Arrays - Heaps are typically stored in arrays for efficiency. Understanding array indexing is essential for heap operations.
• Stacks and Queues - Priority queues (implemented with heaps) extend queue concepts with priority ordering.
• Time & Space Complexity - Understanding complexity analysis helps compare heaps vs sorted arrays vs BSTs for different operations.
• Graphs - Heaps are used in graph algorithms like Dijkstra's shortest path. Understanding heaps helps with graph algorithms.