Heap Concept Structure and Properties in DSA Typescript

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 pile of boxes stacked so that the biggest box is always on top, and every box below is smaller than the one above it.

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

Array form: [10, 7, 9, 5, 6, 8, 4]

Dry Run Walkthrough

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

Goal: Rearrange the array so the largest value is at the root and each parent is larger than its children

Step 1: Start heapify from last parent node at index 2 (value 4)

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

Why: Swap 4 with larger child 9 to satisfy max heap property

Step 2: Heapify node at index 1 (value 10) - no change needed

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

Why: 10 is already larger than children 7 and 6

Step 3: Heapify root node at index 0 (value 5), swap with largest child 10

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

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

Step 4: Heapify node at index 1 (value 5), swap with largest child 7

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

Why: After root swap, fix subtree to maintain heap property

Result:

Final max heap array: [10, 7, 9, 5, 6, 8, 4]

Annotated Code

DSA Typescript

class MaxHeap {
  heap: number[];

  constructor(arr: number[]) {
    this.heap = arr;
    this.buildHeap();
  }

  buildHeap() {
    const startIdx = Math.floor(this.heap.length / 2) - 1;
    for (let i = startIdx; i >= 0; i--) {
      this.heapify(i);
    }
  }

  heapify(i: number) {
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    let largest = i;

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

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

    if (largest !== i) {
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      this.heapify(largest);
    }
  }

  printHeap() {
    console.log(this.heap.join(", "));
  }
}

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

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

Find last parent node to start heapify bottom-up

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

Heapify each parent node to build max heap

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

Check if left child is larger than current largest

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

Check if right child is larger than current largest

if (largest !== i) { swap and recurse heapify(largest); }

Swap parent with largest child and fix subtree

Output

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

Complexity Analysis

Time: O(n) because building a heap from an array requires heapifying nodes bottom-up, which is more efficient than repeated insertions

Space: O(1) because heapify is done in place without extra storage

vs Alternative: Naive approach inserting elements one by one into an empty heap costs O(n log n), slower than bottom-up heapify

Edge Cases

Empty array

Heap remains empty without errors

DSA Typescript

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

Single element array

Heap is the single element itself, no swaps needed

DSA Typescript

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

All elements equal

Heap structure remains unchanged as all parents equal children

DSA Typescript

if (this.heap[left] > this.heap[largest]) and if (this.heap[right] > 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, recognize the heap pattern because it organizes data in a tree with parent-child size rules.

Common Mistakes

Mistake: Starting heapify from the root instead of the last parent node
Fix: Start heapify from the last parent node at index floor(n/2)-1 and move upwards

Mistake: Not swapping parent with the largest child when heap property is violated
Fix: Always swap parent with the largest child and recursively heapify the affected subtree

Summary

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

Use a heap when you need fast access to the largest or smallest element and efficient insertion or removal.

The key insight is that heapify from the bottom up fixes local violations to build a global heap efficiently.