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

Mental Model

A min heap 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 (smallest on top):
      1
     / \
    3   5
   / \
  7   9

Max Heap (largest on top):
      9
     / \
    7   5
   / \
  3   1

Dry Run Walkthrough

Input: array: [5, 3, 9, 1, 7], build min heap and max heap

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

Step 1: Insert 5 as root in both heaps

Min Heap: 5 -> null
Max Heap: 5 -> null

Why: Start with first element as root

Step 2: Insert 3, compare with root, swap in min heap; compare and no swap in max heap

Min Heap: 3 -> 5 -> null
Max Heap: 5 -> 3 -> null

Why: Min heap keeps smallest on top, max heap keeps largest on top

Step 3: Insert 9, no swap in min heap; swap with root in max heap

Min Heap: 3 -> 5 -> 9 -> null
Max Heap: 9 -> 3 -> 5 -> null

Why: Min heap root is smallest, max heap root is largest

Step 4: Insert 1, swap up to root in min heap; no swap in max heap

Min Heap: 1 -> 3 -> 9 -> 5 -> null
Max Heap: 9 -> 3 -> 5 -> 1 -> null

Why: 1 is smallest, so min heap moves it to top

Step 5: Insert 7, no swap in min heap; swap with 3 in max heap

Min Heap: 1 -> 3 -> 9 -> 5 -> 7 -> null
Max Heap: 9 -> 7 -> 5 -> 1 -> 3 -> null

Why: Max heap moves larger 7 up to keep largest on top

Result:

Min Heap final: 1 -> 3 -> 9 -> 5 -> 7 -> null
Max Heap final: 9 -> 7 -> 5 -> 1 -> 3 -> null

Annotated Code

DSA Javascript

class Heap {
  constructor(compare) {
    this.data = [];
    this.compare = compare;
  }

  insert(value) {
    this.data.push(value);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.data.length - 1;
    while (index > 0) {
      let 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; // move up to parent
      } else {
        break; // heap property satisfied
      }
    }
  }

  toString() {
    return this.data.join(' -> ') + ' -> null';
  }
}

// Min heap: smaller value has higher priority
const minHeap = new Heap((a, b) => a < b);
// Max heap: larger value has higher priority
const maxHeap = new Heap((a, b) => a > b);

const values = [5, 3, 9, 1, 7];
for (const val of values) {
  minHeap.insert(val);
  maxHeap.insert(val);
}

console.log('Min Heap final:', minHeap.toString());
console.log('Max Heap final:', maxHeap.toString());

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

compare current node with parent to decide if swap needed

[this.data[index], this.data[parentIndex]] = [this.data[parentIndex], this.data[index]];

swap current node with parent to maintain heap property

index = parentIndex; // move up to parent

advance index upward to continue checking heap property

Output

Min Heap final: 1 -> 3 -> 9 -> 5 -> 7 -> null

Max Heap final: 9 -> 7 -> 5 -> 1 -> 3 -> null

Complexity Analysis

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

Space: O(n) because we 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 Javascript

for (const val of values) { ... } handles empty array by skipping loop

all elements equal

heap structure still valid, order of equal elements maintained by insertion order

DSA Javascript

if (this.compare(this.data[index], this.data[parentIndex])) { ... } no swap if equal

single element

heap contains one element, no bubbling needed

DSA Javascript

while (index > 0) { ... } loop skipped if index is 0

When to Use This Pattern

When a problem asks for quick access to the smallest or largest element repeatedly, use a min heap or max heap respectively to efficiently track that value.

Common Mistakes

Mistake: Using the wrong comparison function causing min heap to behave like max heap or vice versa
Fix: Ensure the compare function correctly returns true when the child should move up (a < b for min heap, a > b for max heap)

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 comparison function that decides which element moves up to maintain heap order.