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.

Practice

1. What is the main difference between a Min Heap and a Max Heap?

easy

A. Min Heap stores elements in ascending order, Max Heap stores elements in descending order.

B. Min Heap always has the smallest element at the root, Max Heap has the largest at the root.

C. Min Heap is used only for numbers, Max Heap only for strings.

D. Min Heap and Max Heap are the same data structure with different names.

Solution

1. Step 1: Understand heap root property

   A Min Heap keeps the smallest element at the root, while a Max Heap keeps the largest element at the root.

2. Step 2: Compare heap ordering

   Min Heap ensures parent nodes are smaller than children; Max Heap ensures parent nodes are larger than children.

3. Final Answer:

   Min Heap always has the smallest element at the root, Max Heap has the largest at the root. -> Option B

4. Quick Check:

   Heap root property = Min smallest, Max largest [OK]

Hint: Min root is smallest, Max root is largest [OK]

Common Mistakes:

• Confusing heap ordering with sorted arrays
• Thinking Min Heap stores ascending order fully
• Assuming heaps only store numbers

2. Which of the following is the correct TypeScript syntax to create a Min Heap using a priority queue library?

easy

A. const minHeap = new PriorityQueue((a, b) => a > b);

B. const minHeap = new PriorityQueue((a, b) => b < a);

C. const minHeap = new PriorityQueue((a, b) => a === b);

D. const minHeap = new PriorityQueue((a, b) => a < b);

Solution

1. Step 1: Understand comparator for Min Heap

   Min Heap comparator returns true if first element is less than second to keep smallest on top.

2. Step 2: Match comparator syntax

   The comparator (a, b) => a < b correctly orders elements for a Min Heap.

3. Final Answer:

   const minHeap = new PriorityQueue((a, b) => a < b); -> Option D

4. Quick Check:

   Min Heap comparator uses < for ordering [OK]

Hint: Min Heap comparator uses less than operator [OK]

Common Mistakes:

• Using greater than comparator for Min Heap
• Using equality comparator which breaks ordering
• Reversing comparator logic

3. Given the following TypeScript code using a Max Heap, what will be the output after inserting elements 3, 10, 5, 1?

medium

A. [10, 5, 3, 1]

B. [1, 3, 5, 10]

C. [3, 1, 5, 10]

D. [5, 10, 3, 1]

Solution

1. Step 1: Insert elements into Max Heap

   Insert 3, then 10 (bubbles up to root), then 5, then 1. Max Heap root is largest element.

2. Step 2: Visualize heap array after insertions

   Heap array after insertions: root 10, children 5 and 3, last element 1.

3. Final Answer:

   [10, 5, 3, 1] -> Option A

4. Quick Check:

   Max Heap root largest = 10 [OK]

Hint: Max Heap root is largest inserted element [OK]

Common Mistakes:

• Assuming insertion order equals array order
• Confusing Min Heap output with Max Heap
• Ignoring heap property after insertions

4. You wrote this TypeScript code to create a Min Heap but it behaves like a Max Heap. What is the bug?

const heap = new PriorityQueue((a, b) => a > b);
heap.insert(4);
heap.insert(2);
heap.insert(7);
console.log(heap.peek());

medium

A. peek() returns wrong element, use pop() instead.

B. Insert method is incorrect, should be insertMin.

C. Comparator should use < instead of > for Min Heap.

D. PriorityQueue class does not support comparator functions.

Solution

1. Step 1: Analyze comparator function

   The comparator (a, b) => a > b causes Max Heap behavior because it prioritizes larger elements.

2. Step 2: Correct comparator for Min Heap

   To get Min Heap behavior, comparator must be (a, b) => a < b so smaller elements rise to top.

3. Final Answer:

   Comparator should use < instead of > for Min Heap. -> Option C

4. Quick Check:

   Min Heap comparator uses < operator [OK]

Hint: Min Heap comparator must use less than [OK]

Common Mistakes:

• Using wrong comparator sign
• Confusing peek() with pop()
• Assuming insert method name affects heap type

5. You need to efficiently find the top 3 smallest numbers from a large stream of data. Which heap type and approach is best?

hard

A. Use a Max Heap of size 3 to keep track of smallest numbers seen so far.

B. Use a Min Heap of size 3 to keep track of smallest numbers seen so far.

C. Use a Max Heap of full data to sort all numbers then pick top 3.

D. Use a Min Heap of full data to sort all numbers then pick top 3.

Solution

1. Step 1: Understand problem requirement

   We want top 3 smallest numbers from a large stream without storing all data.

2. Step 2: Choose heap type and size

   Use a Max Heap of size 3 to keep the current smallest 3 numbers. If new number is smaller than heap root, replace root.

3. Step 3: Why Max Heap?

   Max Heap root is largest among the 3 smallest, so it is easy to discard larger numbers efficiently.

4. Final Answer:

   Use a Max Heap of size 3 to keep track of smallest numbers seen so far. -> Option A

5. Quick Check:

   Top k smallest = Max Heap size k [OK]

Hint: Use max heap size k to track k smallest [OK]

Common Mistakes:

• Using Min Heap size k which grows too large
• Sorting full data which is inefficient
• Using wrong heap type for top k smallest