Min Heap vs Max Heap When to Use Which in DSA Typescript - Trade-offs & Analysis

Mental Model

A min heap always keeps the smallest item on top, while a max heap keeps the largest item on top. This helps quickly find the smallest or largest value.

Analogy: Think of a min heap like a line where the shortest person is always at the front, and a max heap like a line where the tallest person is always at the front.

Min Heap:
    1
   / \
  3   5
 / \
4   8

Max Heap:
    8
   / \
  5   3
 / \
1   4

Dry Run Walkthrough

Input: array: [5, 3, 8, 1, 4], build min heap and max heap

Goal: Show how min heap and max heap organize the same data differently to quickly access smallest or largest value

Step 1: Insert 5 into empty min heap

5

Why: Start building min heap with first element

Step 2: Insert 3, swap with 5 to keep smallest on top

3 -> 5

Why: 3 is smaller than 5, so it moves up to keep min heap property

Step 3: Insert 8, no swap needed

3 -> 5, 8

Why: 8 is larger than 3, so it stays as child

Step 4: Insert 1, swap with 3 to keep smallest on top

1 -> 3, 8 -> 5

Why: 1 is smallest, so it moves to root

Step 5: Insert 4, no swap needed

1 -> 3, 8 -> 5, 4

Why: 4 is larger than 1 and 3, so it stays as child

Step 6: Build max heap from same array

8 -> 5, 3 -> 1, 4

Why: Largest value 8 moves to root to keep max heap property

Result:

Min Heap: 1 -> 3, 8 -> 5, 4
Max Heap: 8 -> 5, 3 -> 1, 4

Annotated Code

DSA Typescript

class Heap {
  data: number[] = [];
  isMinHeap: boolean;

  constructor(isMinHeap: boolean) {
    this.isMinHeap = isMinHeap;
  }

  private compare(a: number, b: number): boolean {
    return this.isMinHeap ? a < b : a > b;
  }

  insert(value: number) {
    this.data.push(value);
    this.bubbleUp(this.data.length - 1);
  }

  private bubbleUp(index: number) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.compare(this.data[index], this.data[parentIndex])) {
        [this.data[index], this.data[parentIndex]] = [this.data[parentIndex], this.data[index]];
        index = parentIndex;
      } else {
        break;
      }
    }
  }

  printHeap() {
    console.log(this.data.join(' -> '));
  }
}

// Driver code
const values = [5, 3, 8, 1, 4];

const minHeap = new Heap(true);
values.forEach(v => minHeap.insert(v));
console.log('Min Heap:');
minHeap.printHeap();

const maxHeap = new Heap(false);
values.forEach(v => maxHeap.insert(v));
console.log('Max Heap:');
maxHeap.printHeap();

return this.isMinHeap ? a < b : a > b;

decide order based on min or max heap property

this.data.push(value); this.bubbleUp(this.data.length - 1);

insert new value at end and restore heap property by bubbling up

if (this.compare(this.data[index], this.data[parentIndex])) { swap and move index up } else { break; }

swap child with parent if heap property violated, else stop

Output

Min Heap:

1 -> 3 -> 8 -> 5 -> 4

Max Heap:

8 -> 5 -> 3 -> 1 -> 4

Complexity Analysis

Time: O(n log n) because each insert may bubble up through the heap height which is log n, done n times

Space: O(n) to store all elements in the heap array

vs Alternative: Compared to sorting the array which is O(n log n), heaps allow quick access to min or max without full sort

Edge Cases

empty input array

heap remains empty, no errors

DSA Typescript

values.forEach(v => minHeap.insert(v));

all elements equal

heap structure still valid, all elements equal so no swaps needed

DSA Typescript

if (this.compare(this.data[index], this.data[parentIndex])) {

single element array

heap contains one element, no bubbling needed

DSA Typescript

this.bubbleUp(this.data.length - 1);

When to Use This Pattern

When a problem asks for quick access to smallest or largest element repeatedly, reach for min heap or max heap respectively because they keep that element at the top efficiently.

Common Mistakes

Mistake: Confusing min heap and max heap comparison logic
Fix: Use a clear compare function that switches behavior based on heap type

Mistake: Not bubbling up after insert, breaking heap property
Fix: Always call bubbleUp after inserting a new element

Summary

Min heap keeps smallest element on top; max heap keeps largest element on top.

Use min heap when you need quick access to smallest values, max heap for largest values.

The key is the compare function that decides heap order and bubbling up to restore heap property.