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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Min-Heap after insertions?

Consider a Min-Heap implemented as an array. Insert the following numbers in order: 10, 4, 15, 20, 0. What is the array representation of the heap after all insertions?

DSA Typescript

class MinHeap {
  heap: number[] = [];

  insert(val: number) {
    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 [4, 0, 15, 20, 10]

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

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

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

💡 Hint

Remember, in a Min-Heap, the smallest element is always at the root (index 0). After each insertion, the heap property is restored by bubbling up.

After inserting all elements, the heap array is [0, 4, 15, 20, 10]. The smallest element 0 is at the root. The heap property is maintained at every step.

🧠 Conceptual

intermediate

What is the height of a heap with 31 elements?

Given a complete binary heap with 31 elements, what is the height of the heap?

A 4

B 5

C 3

D 6

💡 Hint

The height of a complete binary tree with n nodes is floor(log2(n)).

Height = floor(log2(31)) = 4. It is a perfect binary tree of height 4 (longest path from root to leaf has 4 edges).

🔧 Debug

advanced

Identify the error in this Max-Heap insertion code

What error will this Max-Heap insertion code cause when inserting elements?

DSA Typescript

class MaxHeap {
  heap: number[] = [];

  insert(val: number) {
    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 MaxHeap();
[5, 10, 3].forEach(num => heap.insert(num));
console.log(heap.heap);

A Infinite loop because index never updates.

B The code runs correctly and outputs [10, 5, 3].

C Runtime error due to accessing undefined index in the array.

D The heap property is violated because parentIndex calculation is incorrect.

💡 Hint

Check how parentIndex is calculated for a binary heap stored in an array.

The parent index should be Math.floor((index - 1) / 2), but here it is Math.floor(index / 2), which is incorrect and breaks the heap property.

❓ Predict Output

advanced

What is the output after extracting max from this Max-Heap?

Given a Max-Heap represented as [20, 15, 18, 10, 12, 9], what is the array after extracting the max element once?

DSA Typescript

class MaxHeap {
  heap: number[] = [20, 15, 18, 10, 12, 9];

  extractMax() {
    if (this.heap.length === 0) return null;
    const max = this.heap[0];
    const end = this.heap.pop();
    if (this.heap.length > 0 && end !== undefined) {
      this.heap[0] = end;
      this.sinkDown();
    }
    return max;
  }

  sinkDown() {
    let index = 0;
    const length = this.heap.length;
    const element = this.heap[0];

    while (true) {
      let leftChildIndex = 2 * index + 1;
      let rightChildIndex = 2 * index + 2;
      let leftChild, rightChild;
      let swap = null;

      if (leftChildIndex < length) {
        leftChild = this.heap[leftChildIndex];
        if (leftChild > element) swap = leftChildIndex;
      }

      if (rightChildIndex < length) {
        rightChild = this.heap[rightChildIndex];
        if ((swap === null && rightChild > element) || (swap !== null && rightChild > leftChild!)) {
          swap = rightChildIndex;
        }
      }

      if (swap === null) break;

      this.heap[index] = this.heap[swap];
      this.heap[swap] = element;
      index = swap;
    }
  }
}

const heap = new MaxHeap();
heap.extractMax();
console.log(heap.heap);

A [18, 15, 12, 10, 9]

B [15, 12, 18, 10, 9]

C [18, 15, 9, 10, 12]

D [15, 18, 12, 10, 9]

💡 Hint

After removing the max (root), replace it with the last element and sink it down to restore heap property.

After extracting 20, replace root with last element 9: [9, 15, 18, 10, 12]. Sink down: largest child of root is 18 (index 2) > 15 (index 1). Swap root with 18: [18, 15, 9, 10, 12]. Now at index 2 (9), left child index 5 >= length 5, no children, stop. Final heap: [18, 15, 9, 10, 12].

🧠 Conceptual

expert

How many leaf nodes are in a heap with 1000 elements?

In a complete binary heap with 1000 elements, how many leaf nodes does it have?

A 500

B 501

C 499

D 250

💡 Hint

Leaf nodes in a complete binary tree are the nodes from index floor(n/2) to n-1 (500 nodes).

Number of leaf nodes = n - floor(n/2) = 1000 - 500 = 500.