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].