Build Heap from Array Heapify in DSA Javascript

Mental Model

We turn an unordered list into a heap by fixing each parent node from the bottom up so the heap property holds everywhere.

Analogy: Imagine stacking boxes so that bigger boxes are always below smaller boxes. We start fixing from the bottom shelves up to the top to make sure the stack is stable.

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 every parent is bigger than its children

Step 1: Start heapify from last parent index (1), fix subtree rooted at index 1

[4, 10, 3, 5, 1]

Why: We start from last parent because leaves are already heaps

Step 2: Compare node 10 with children 5 and 1, no swap needed

[4, 10, 3, 5, 1]

Why: Parent 10 is already bigger than children, subtree is heap

Step 3: Move to parent index 0, fix subtree rooted at 4

[4, 10, 3, 5, 1]

Why: We fix from bottom up to ensure heap property

Step 4: Compare 4 with children 10 and 3, swap 4 with 10

[10, 4, 3, 5, 1]

Why: Parent must be bigger, so swap with largest child

Step 5: Fix subtree rooted at index 1 (value 4), compare with children 5 and 1, swap 4 with 5

[10, 5, 3, 4, 1]

Why: After swap, subtree might break heap, so fix recursively

Step 6: Fix subtree rooted at index 3 (value 4), no children to compare

[10, 5, 3, 4, 1]

Why: Leaf node reached, heap property holds

Result:

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

Annotated Code

DSA Javascript

class MaxHeap {
  constructor(array) {
    this.heap = array;
    this.buildHeap();
  }

  buildHeap() {
    const n = this.heap.length;
    // Start from last parent node and heapify down to root
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
      this.heapify(i);
    }
  }

  heapify(i) {
    const n = this.heap.length;
    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 parent, swap and heapify subtree
    if (largest !== i) {
      [this.heap[i], this.heap[largest]] = [this.heap[largest], this.heap[i]];
      this.heapify(largest);
    }
  }

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

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

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

start heapify from last parent to root

this.heapify(i);

fix subtree rooted at i to maintain heap property

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

check if left child is bigger than current largest

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

check if right child is bigger than current largest

if (largest !== i) {

if parent is not largest, swap and heapify child subtree

this.heapify(largest);

recursively fix subtree after swap

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) worst 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 is O(n log n), so this bottom-up heapify is faster

Edge Cases

empty array

buildHeap does nothing and heap remains empty

DSA Javascript

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

array with one element

heapify runs once but no swaps needed, heap is the same

DSA Javascript

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

array with all equal elements

no swaps happen, heap property holds trivially

DSA Javascript

if (largest !== i) {

When to Use This Pattern

When you need to build a heap quickly from an unordered array, use bottom-up heapify starting from last parent to root to efficiently enforce heap property.

Common Mistakes

Mistake: Starting heapify from index 0 instead of last parent causes unnecessary work and incorrect heap
Fix: Start heapify from Math.floor(n/2) - 1 down to 0 to only fix parents

Mistake: Not recursively heapifying after swap breaks heap property in subtrees
Fix: Call heapify recursively on the swapped child's index

Summary

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

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

Start heapify from last parent node down to root, recursively fixing subtrees after swaps.

Practice

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

easy

A. To reverse the array elements

B. To sort the array in ascending order

C. To find the maximum element in the array

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 each parent node is greater (max-heap) or smaller (min-heap) than its children.

2. Step 2: Role of heapify

   Heapify rearranges elements so the heap property holds for every subtree, starting from a node downwards.

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 subtree to maintain heap order [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 way to start heapifying an array arr of length n in JavaScript to build a max heap?

easy

A. for(let i = 0; i < n; i++) heapify(arr, i, n);

B. for(let i = 1; i < n; i++) heapify(arr, i, n);

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

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

Solution

1. Step 1: Identify heapify start index

   Heapify starts from the last non-leaf node, which is at index Math.floor(n/2) - 1.

2. Step 2: Loop backwards to root

   We heapify each node from this index down to 0 to ensure the entire tree satisfies heap property.

3. Final Answer:

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

4. Quick Check:

   Start heapify at last non-leaf node [OK]

Hint: Start heapify from last parent node backwards [OK]

Common Mistakes:

• Starting heapify from index 0 forwards
• Heapifying leaf nodes unnecessarily
• Using incorrect loop boundaries

3. Given the array [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. [9, 4, 5, 3, 1, 2]

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

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

Solution

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

   Heapify at index 2: children are indices 5 (5) and no right child. 2 < 5, swap to get [3,9,5,1,4,2].

2. Step 2: Heapify at index 1

   Children at indices 3 (1) and 4 (4). 9 > 4 and 1, no swap needed.

3. Step 3: Heapify at index 0

   Children at indices 1 (9) and 2 (5). 3 < 9, swap 3 and 9: [9,3,5,1,4,2]. Heapify at index 1 again: children 3 (1) and 4 (4). 3 < 4, swap: [9,4,5,1,3,2].

4. Final Answer:

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

5. Quick Check:

   Max heap root is 9, children smaller [OK]

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

Common Mistakes:

• Not heapifying children after swap
• Swapping with wrong child
• Stopping heapify too early

4. Consider this heapify function snippet in JavaScript:

function heapify(arr, i, n) {
  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, largest, n);
  }
}

What is the bug if the function is called with heapify(arr, 0, arr.length - 1) instead of heapify(arr, 0, arr.length)?

medium

A. It will ignore the last element of the array during heapify

B. It will cause an infinite recursion

C. It will throw a syntax error

D. It will heapify the entire array correctly

Solution

1. Step 1: Understand parameter n meaning

   Parameter n is the array length limit for heapify to avoid out-of-bound access.

2. Step 2: Effect of passing arr.length - 1

   Passing arr.length - 1 excludes the last element index (n-1) from heapify checks, so last element is ignored.

3. Final Answer:

   It will ignore the last element of the array during heapify -> Option A

4. Quick Check:

   n must be array length, not length-1 [OK]

Hint: Use full array length as heapify limit [OK]

Common Mistakes:

• Confusing length and last index
• Expecting syntax error instead of logic error
• Ignoring off-by-one errors

5. You have an array [4, 10, 3, 5, 1] and want to build a min heap using heapify. Which of the following changes is necessary in the heapify function to build a min heap instead of a max heap?

hard

A. Swap the left and right child indices calculations

B. Change comparisons from '>' to '<' when comparing children with parent

C. Change comparisons from '<' to '>' when comparing children with parent

D. No change needed; heapify works for both min and max heaps

Solution

1. Step 1: Understand max vs min heap comparison

   Max heap keeps parent >= children; min heap keeps parent <= children.

2. Step 2: Adjust comparison operators

   To build min heap, change '>' to '<' so parent is smaller than children.

3. Final Answer:

   Change comparisons from '>' to '<' when comparing children with parent -> Option B

4. Quick Check:

   Min heap uses less-than comparisons [OK]

Hint: Flip comparison signs for min heap [OK]

Common Mistakes:

• Swapping child indices instead of comparisons
• Leaving comparisons unchanged
• Assuming heapify auto-detects heap type