Build Heap from Array Heapify in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Min-Heap after buildHeap

What is the printed state of the min-heap array after running the buildHeap function on the input array?

DSA Javascript

function buildMinHeap(arr) {
  const n = arr.length;
  function heapify(i) {
    let smallest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && arr[left] < arr[smallest]) smallest = left;
    if (right < n && arr[right] < arr[smallest]) smallest = right;
    if (smallest !== i) {
      [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
      heapify(smallest);
    }
  }
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(i);
  }
  return arr;
}

const input = [9, 4, 7, 1, -2, 6, 5];
const heap = buildMinHeap(input);
console.log(heap);

A [1, -2, 5, 4, 9, 6, 7]

B [-2, 1, 5, 9, 4, 6, 7]

C [-2, 1, 6, 4, 9, 5, 7]

D [1, 4, 5, 9, -2, 6, 7]

💡 Hint

Remember that buildHeap starts heapifying from the last parent node up to the root.

The buildMinHeap function heapifies from the last parent node to the root, ensuring the smallest element is at the root. After heapify, the array represents a valid min-heap.

❓ Predict Output

intermediate

Max-Heap Array after Heapify

What is the state of the array after building a max-heap from the given input array?

DSA Javascript

function buildMaxHeap(arr) {
  const n = arr.length;
  function heapify(i) {
    let largest = i;
    const left = 2 * i + 1;
    const 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(largest);
    }
  }
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    heapify(i);
  }
  return arr;
}

const input = [3, 9, 2, 1, 4, 5];
const heap = buildMaxHeap(input);
console.log(heap);

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

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

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

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

💡 Hint

Max-heap means parent nodes are always greater than children.

After heapify, the largest element is at the root and the array satisfies max-heap property.

🔧 Debug

advanced

Identify the Bug in Heapify Function

The following heapify function is intended to build a min-heap but produces incorrect output. What is the bug?

DSA Javascript

function heapify(arr, n, i) {
  let smallest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
  if (left < n && arr[left] > arr[smallest]) smallest = left;
  if (right < n && arr[right] > arr[smallest]) smallest = right;
  if (smallest !== i) {
    [arr[i], arr[smallest]] = [arr[smallest], arr[i]];
    heapify(arr, n, smallest);
  }
}

A The swap operation is missing

B The indices for left and right children are incorrect

C The comparison operators should be '<' to build a min-heap, not '>'

D The recursive call should be heapify(arr, smallest, n)

💡 Hint

Check the comparison signs for min-heap property.

For min-heap, parent should be smaller than children, so comparisons must use '<' to find the smallest child.

🧠 Conceptual

advanced

Time Complexity of Build Heap

What is the time complexity of building a heap from an unsorted array using the heapify method?

A O(n log n)

B O(log n)

C O(n^2)

D O(n)

💡 Hint

Consider that heapify is called on all non-leaf nodes and work done decreases at lower levels.

Building a heap using heapify runs in O(n) time because the work done at each level decreases geometrically.

🚀 Application

expert

Resulting Heap After Multiple Insertions

Starting with an empty max-heap, insert the elements [4, 10, 3, 5, 1] one by one. What is the heap array after all insertions?

DSA Javascript

class MaxHeap {
  constructor() {
    this.heap = [];
  }
  insert(val) {
    this.heap.push(val);
    let i = this.heap.length - 1;
    while (i > 0) {
      let parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] < this.heap[i]) {
        [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
        i = parent;
      } else {
        break;
      }
    }
  }
}

const heap = new MaxHeap();
[4, 10, 3, 5, 1].forEach(x => heap.insert(x));
console.log(heap.heap);

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

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

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

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

💡 Hint

After each insertion, the new element bubbles up to maintain max-heap property.

Inserting elements one by one and bubbling up results in the heap array [10, 5, 3, 4, 1].

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