Build Heap from Array Heapify in DSA Typescript

Mental Model

We turn an unordered list into a heap by fixing each subtree from the bottom up, ensuring the heap property holds everywhere.

Analogy: Imagine organizing a messy pile of books into neat stacks by starting from the bottom shelves and fixing each shelf so heavier books are below lighter ones.

Array: [4, 10, 3, 5, 1]
Heap tree:
       4
     /   \
   10     3
  /  \
 5    1

Dry Run Walkthrough

Input: array: [4, 10, 3, 5, 1]

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

Step 1: Start heapify at index 1 (value 10), fix subtree

[4, 10, 3, 5, 1]

Why: We start from the last non-leaf node to ensure subtrees below are heaps

Step 2: Heapify at index 0 (value 4), compare with children 10 and 3

[4, 10, 3, 5, 1]

Why: Parent 4 is smaller than left child 10, so swap to fix heap property

Step 3: Swap 4 and 10, array becomes [10, 4, 3, 5, 1]

[10, 4, 3, 5, 1]

Why: After swap, heap property restored at root, but subtree at index 1 may need fixing

Step 4: Heapify at index 1 (value 4), compare with children 5 and 1

[10, 4, 3, 5, 1]

Why: 4 is smaller than left child 5, so swap needed

Step 5: Swap 4 and 5, array becomes [10, 5, 3, 4, 1]

[10, 5, 3, 4, 1]

Why: After swap, subtree rooted at index 3 is a leaf, so heap property holds

Result:

Final heap array: [10, 5, 3, 4, 1]

Annotated Code

DSA Typescript

class MaxHeap {
  heap: number[];

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

  private buildHeap(): void {
    const n = this.heap.length;
    // Start from last non-leaf node and heapify each
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      this.heapify(i, n);
    }
  }

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

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

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

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

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

// Driver code
const arr = [4, 10, 3, 5, 1];
const maxHeap = new MaxHeap(arr);
maxHeap.printHeap();

for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {

start heapify from last non-leaf node up to root

this.heapify(i, n);

fix subtree rooted at i to maintain max-heap property

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

check if left child is larger than current largest

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

check if right child is larger than current largest

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

swap and recursively heapify affected subtree

Output

10, 5, 3, 4, 1

Complexity Analysis

Time: O(n) because heapify is called on n/2 nodes and each call takes O(log n) in worst case but overall sums to O(n)

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

vs Alternative: Naive approach inserting elements one by one into heap takes O(n log n), so this bottom-up heapify is more efficient

Edge Cases

empty array

buildHeap does nothing and heap remains empty

DSA Typescript

for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {

array with one element

heapify loop runs zero times, heap is the same single element

DSA Typescript

for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {

array with all equal elements

heapify swaps are never triggered, heap remains unchanged

DSA Typescript

if (largest !== i) {

When to Use This Pattern

When you need to build a heap from an unordered array efficiently, use bottom-up heapify starting from last non-leaf node to root to fix subtrees.

Common Mistakes

Mistake: Starting heapify from the root instead of last non-leaf node
Fix: Start from index Math.floor(n/2)-1 down to 0 to ensure all subtrees are fixed

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

Summary

Builds a max-heap from an unordered array by fixing subtrees bottom-up.

Use when you want to efficiently convert an array into a heap for heap operations.

Start heapify from the last non-leaf node and fix each subtree to maintain heap property.