Heap Concept Structure and Properties in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Min-Heap insertion sequence?

Consider an empty Min-Heap. Insert the numbers 10, 4, 15, 20, 0 in this order. What is the heap array representation after all insertions?

DSA Javascript

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(val) {
    this.heap.push(val);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }
}

const heap = new MinHeap();
[10, 4, 15, 20, 0].forEach(num => heap.insert(num));
console.log(heap.heap);

A [0, 4, 15, 20, 10]

B [10, 4, 15, 20, 0]

C [4, 0, 15, 20, 10]

D [0, 10, 15, 20, 4]

💡 Hint

Remember that in a Min-Heap, the smallest element is always at the root, and after each insertion, the heap property is restored by bubbling up.

After inserting 10, heap is [10]. Insert 4, bubble up swaps 4 and 10 → [4,10]. Insert 15, no bubble up needed → [4,10,15]. Insert 20, no bubble up → [4,10,15,20]. Insert 0, bubble up swaps 0 with 10, then with 4 → [0,4,15,20,10].

🧠 Conceptual

intermediate

Which property must a Max-Heap always satisfy?

Select the correct property that a Max-Heap must always satisfy.

A Every parent node is greater than or equal to its children.

B Every parent node is less than or equal to its children.

C All leaf nodes have the same value.

D The tree is always a complete binary tree but values can be random.

💡 Hint

Think about what makes a Max-Heap different from other binary trees.

A Max-Heap requires that each parent node is greater than or equal to its children to maintain the heap property. The tree is also complete, but the key property is about parent-child value relation.

🔧 Debug

advanced

Identify the error in this heapify function for Max-Heap

What error will this JavaScript code cause when heapifying an array into a Max-Heap?

DSA Javascript

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

const arr = [3, 9, 2, 1, 4, 5];
heapify(arr, arr.length, 0);
console.log(arr);

A The function produces a sorted array instead of a heap.

B The function causes a stack overflow due to infinite recursion.

C The function swaps elements incorrectly causing a TypeError.

D The function only heapifies the subtree rooted at index 0, not the entire array, so the array won't be a valid Max-Heap.

💡 Hint

Heapifying an entire array requires calling heapify on all non-leaf nodes, not just the root.

The code only heapifies the subtree rooted at index 0. To build a Max-Heap from an array, heapify must be called on all non-leaf nodes from bottom up. Otherwise, the array won't satisfy the heap property fully.

🚀 Application

advanced

What is the height of a complete binary heap with 1000 elements?

A complete binary heap has 1000 elements. What is the height of this heap?

A 10

B 9

C 8

D 11

💡 Hint

Height of a complete binary heap with n elements is floor(log2(n)).

The height of a complete binary heap with n elements is floor(log2(n)). For n=1000, log2(1000) ≈ 9.96, so floor(9.96) = 9.

❓ Predict Output

expert

What is the output after extracting the root from this Min-Heap?

Given the Min-Heap array [1, 3, 6, 5, 9, 8], what is the array after extracting the root (minimum element) once?

DSA Javascript

function extractMin(heap) {
  if (heap.length === 0) return null;
  const min = heap[0];
  heap[0] = heap.pop();
  let i = 0;
  while (true) {
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let smallest = i;
    if (left < heap.length && heap[left] < heap[smallest]) smallest = left;
    if (right < heap.length && heap[right] < heap[smallest]) smallest = right;
    if (smallest === i) break;
    [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
    i = smallest;
  }
  return min;
}

const heap = [1, 3, 6, 5, 9, 8];
extractMin(heap);
console.log(heap);

A [3, 5, 6, 9, 8]

B [6, 3, 8, 5, 9]

C [3, 5, 6, 8, 9]

D [5, 3, 6, 8, 9]

💡 Hint

After removing the root, replace it with the last element and bubble down to restore heap property.

Remove 1, replace root with 8 → [8,3,6,5,9]. Bubble down swaps 8 with 3 → [3,8,6,5,9]. Then 8 swaps with 5 → [3,5,6,8,9]. Final heap is [3,5,6,8,9].