Heap Concept Structure and Properties in DSA Javascript

Mental Model

A heap is a special tree where each parent is bigger (or smaller) than its children, making it easy to find the biggest or smallest item quickly.

Analogy: Imagine a family tree where every parent is taller than their children, so the tallest person is always at the top, making it easy to find the tallest family member.

       10
      /  \
     7    9
    / \  / \
   5  6 8  4

Dry Run Walkthrough

Input: Build a max-heap from array [5, 9, 8, 4, 7, 6, 10]

Goal: Rearrange the array into a max-heap where each parent is greater than its children

Step 1: Start from the last parent node at index 2 (value 8), compare with children and swap with largest child if needed

[5, 9, 10, 4, 7, 6, 8]

Why: We fix the subtree rooted at index 2 to satisfy max-heap property

Step 2: Move to parent node at index 1 (value 9), compare with children and swap if needed

[5, 9, 10, 4, 7, 6, 8]

Why: No swap needed because 9 is greater than children 4 and 7

Step 3: Move to root node at index 0 (value 5), compare with children and swap with largest child (10)

[10, 9, 5, 4, 7, 6, 8]

Why: Root must be largest, so swap with largest child 10

Step 4: Fix subtree rooted at index 2 (value 5), swap with largest child (8)

[10, 9, 8, 4, 7, 6, 5]

Why: After root swap, fix subtree to maintain max-heap

Result:

[10, 9, 8, 4, 7, 6, 5] -- max-heap formed

Annotated Code

DSA Javascript

class MaxHeap {
  constructor() {
    this.heap = [];
  }

  // Swap two elements in the heap array
  swap(i, j) {
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
  }

  // Heapify subtree rooted at index i
  heapify(i) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;

    // Check if left child is larger
    if (left < this.heap.length && this.heap[left] > this.heap[largest]) {
      largest = left;
    }

    // Check if right child is larger
    if (right < this.heap.length && this.heap[right] > this.heap[largest]) {
      largest = right;
    }

    // If largest is not root, swap and continue heapifying
    if (largest !== i) {
      this.swap(i, largest);
      this.heapify(largest);
    }
  }

  // Build max heap from array
  buildHeap(arr) {
    this.heap = arr.slice();
    const start = Math.floor(this.heap.length / 2) - 1;

    // Heapify from last parent to root
    for (let i = start; i >= 0; i--) {
      this.heapify(i);
    }
  }

  // Print heap as array
  printHeap() {
    console.log(this.heap);
  }
}

// Driver code
const arr = [5, 9, 8, 4, 7, 6, 10];
const maxHeap = new MaxHeap();
maxHeap.buildHeap(arr);
maxHeap.printHeap();

if (left < this.heap.length && this.heap[left] > this.heap[largest]) {

Check if left child is bigger than current largest

if (right < this.heap.length && this.heap[right] > this.heap[largest]) {

Check if right child is bigger than current largest

if (largest !== i) { this.swap(i, largest); this.heapify(largest); }

Swap with largest child and heapify subtree to maintain max-heap

for (let i = start; i >= 0; i--) { this.heapify(i); }

Build heap by heapifying all parent nodes from bottom up

Output

[10, 9, 8, 4, 7, 6, 5]

Complexity Analysis

Time: O(n) because heapify is called on all parent nodes and each heapify takes O(log n) but overall buildHeap is O(n)

Space: O(n) because we store the heap array of size n

vs Alternative: Building a heap by inserting elements one by one is O(n log n), so this bottom-up heapify is more efficient

Edge Cases

Empty array

Heap remains empty without errors

DSA Javascript

const start = Math.floor(this.heap.length / 2) - 1;

Single element array

Heap is the same single element

DSA Javascript

for (let i = start; i >= 0; i--) { this.heapify(i); }

All elements equal

Heap remains unchanged as all parents equal children

DSA Javascript

if (this.heap[left] > this.heap[largest])

When to Use This Pattern

When you need quick access to the largest or smallest item and want to maintain order efficiently, use a heap because it keeps the biggest or smallest at the top.

Common Mistakes

Mistake: Starting heapify from index 0 instead of last parent node
Fix: Start heapify from Math.floor(n/2) - 1 to cover all parents

Mistake: Not recursively heapifying after swap
Fix: Call heapify again on the swapped child's index to fix subtree

Summary

A heap is a tree where parents are always bigger (max-heap) or smaller (min-heap) than their children.

Use a heap when you want fast access to the largest or smallest element in a collection.

The key is to fix the tree from bottom up so each parent is bigger than its children, making the top the biggest.