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.

Practice

1. What is the main purpose of the heapify process when building a heap from an array?

easy

A. To find the maximum element in the array

B. To sort the array in ascending order

C. To reverse the array elements

D. To rearrange the array elements to satisfy the heap property

Solution

1. Step 1: Understand heap property

   A heap is a special tree where parent nodes follow a specific order compared to children (max-heap or min-heap).

2. Step 2: Role of heapify

   Heapify rearranges elements so that the heap property holds for every subtree, starting from the bottom.

3. Final Answer:

   To rearrange the array elements to satisfy the heap property -> Option D

4. Quick Check:

   Heapify = Rearrange for heap property [OK]

Hint: Heapify fixes order to build a valid heap fast [OK]

Common Mistakes:

• Thinking heapify sorts the array
• Confusing heapify with finding max element
• Assuming heapify reverses the array

2. Which of the following is the correct TypeScript syntax to start heapifying from the last non-leaf node in an array arr of length n?

easy

A. for(let i = Math.floor(n / 2); i < n; i++) { heapify(arr, n, i); }

B. for(let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); }

C. for(let i = n - 1; i >= 0; i--) { heapify(arr, n, i); }

D. for(let i = 0; i < n; i++) { heapify(arr, n, i); }

Solution

1. Step 1: Identify last non-leaf node index

   In a heap array, last non-leaf node is at index Math.floor(n/2) - 1.

2. Step 2: Loop from last non-leaf to root

   We heapify from this index down to 0 to ensure all subtrees satisfy heap property.

3. Final Answer:

   for(let i = Math.floor(n / 2) - 1; i >= 0; i--) { heapify(arr, n, i); } -> Option B

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify at Math.floor(n/2)-1 down to 0 [OK]

Common Mistakes:

• Starting heapify from 0 upwards
• Starting heapify from last element
• Looping beyond last non-leaf node

3. Given the array arr = [3, 9, 2, 1, 4, 5], what is the array after building a max-heap using heapify?

medium

A. [9, 4, 5, 1, 3, 2]

B. [5, 4, 3, 1, 9, 2]

C. [9, 3, 5, 1, 4, 2]

D. [3, 9, 2, 1, 4, 5]

Solution

1. Step 1: Start heapify from index 2 (Math.floor(6/2)-1)

   Heapify at index 2: children 5 (index 5), swap 2 and 5 to get [3,9,5,1,4,2].

2. Step 2: Heapify at index 1 and 0

   Index 1: children 1 and 4, max is 9 at index 1, no swap. Index 0: children 9 and 5, swap 3 and 9. Final array: [9,4,5,1,3,2]

3. Final Answer:

   [9, 4, 5, 1, 3, 2] -> Option A

4. Quick Check:

   Max-heap root is 9, children smaller [OK]

Hint: Heapify bottom-up swaps to fix max-heap [OK]

Common Mistakes:

• Not swapping correctly during heapify
• Confusing min-heap with max-heap
• Leaving original array unchanged

4. Consider this TypeScript code snippet to build a max heap:

function heapify(arr: number[], n: number, i: number) {
  let largest = i;
  let left = 2 * i + 1;
  let right = 2 * i + 2;

  if (left < n && arr[left] > arr[largest]) largest = left;
  if (right < n && arr[right] > arr[largest]) largest = right;

  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}

function buildHeap(arr: number[]) {
  let n = arr.length;
  for (let i = 0; i <= Math.floor(n / 2); i++) {
    heapify(arr, n, i);
  }
}

What is the error in this code?

medium

A. The loop in buildHeap should run from Math.floor(n/2)-1 down to 0

B. The heapify function swaps elements incorrectly

C. The left and right child indices are calculated wrongly

D. The buildHeap function should not call heapify

Solution

1. Step 1: Analyze buildHeap loop range

   The loop runs from 0 up to Math.floor(n/2), but heapify must start from last non-leaf node down to root.

2. Step 2: Correct loop direction and range

   Loop should be: for(let i = Math.floor(n/2) - 1; i >= 0; i--) to ensure all subtrees heapify properly.

3. Final Answer:

   The loop in buildHeap should run from Math.floor(n/2)-1 down to 0 -> Option A

4. Quick Check:

   Heapify bottom-up loop direction matters [OK]

Hint: Loop heapify bottom-up from last non-leaf node [OK]

Common Mistakes:

• Looping heapify top-down instead of bottom-up
• Incorrect child index calculations
• Not swapping elements during heapify

5. You have an array arr = [4, 10, 3, 5, 1, 2]. After building a min-heap using heapify, what will be the array representation?

hard

A. [1, 4, 2, 10, 5, 3]

B. [1, 3, 2, 5, 10, 4]

C. [1, 4, 2, 5, 10, 3]

D. [1, 2, 3, 4, 5, 10]

Solution

1. Step 1: Build min-heap bottom-up

   Start heapify from index 2 (Math.floor(6/2)-1): heapify at index 2 swaps 3 and 2 to get [4,10,2,5,1,3].

2. Step 2: Heapify at index 1 and 0

   At index 1: children 5 and 1, swap 10 and 1 -> [4,1,2,5,10,3]. At index 0: children 1 and 2, swap 4 and 1 -> [1,4,2,5,10,3].

3. Final Answer:

   [1, 4, 2, 5, 10, 3] -> Option C

4. Quick Check:

   Min-heap root is smallest element 1 [OK]

Hint: Min-heap root is smallest; heapify swaps bottom-up [OK]

Common Mistakes:

• Confusing min-heap with max-heap results
• Not swapping correctly during heapify
• Assuming sorted array equals heap