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.

Practice

1. What is a key property of a max-heap data structure?

easy

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 heap is always a complete binary tree with sorted leaves

Solution

1. Step 1: Understand max-heap property

   A max-heap requires each parent node to be greater than or equal to its children to maintain the heap order.

2. Step 2: Compare options with definition

   Every parent node is greater than or equal to its children matches the max-heap property exactly, while others describe min-heap or incorrect properties.

3. Final Answer:

   Every parent node is greater than or equal to its children -> Option A

4. Quick Check:

   Max-heap property = Every parent ≥ children [OK]

Hint: Max-heap means parent ≥ children always [OK]

Common Mistakes:

• Confusing max-heap with min-heap property
• Thinking leaves must be sorted
• Assuming all leaf nodes have same value

2. Which of the following is the correct TypeScript syntax to declare a min-heap using an array?

easy

A. let minHeap = new Heap();

B. const minHeap: number[] = [];

C. const minHeap: Heap = new Heap();

D. var minHeap = [];

Solution

1. Step 1: Identify array declaration syntax in TypeScript

   Declaring an array of numbers uses syntax like const arr: number[] = [];.

2. Step 2: Check options for correct array declaration

   const minHeap: number[] = []; correctly declares an empty number array for min-heap storage. Others either use undefined Heap class or older syntax.

3. Final Answer:

   const minHeap: number[] = []; -> Option B

4. Quick Check:

   Array declaration with type = const arr: number[] = [] [OK]

Hint: Use const name: type[] = [] for array declaration [OK]

Common Mistakes:

• Using undefined Heap class without import
• Using var instead of const or let
• Missing type annotation in TypeScript

3. Given the following TypeScript code for a max-heap array representation:

const heap = [50, 30, 40, 10, 20];
console.log(heap[1]);

What will be the output?

medium

A. 10

B. 50

C. 40

D. 30

Solution

1. Step 1: Understand zero-based indexing in arrays

   Arrays in TypeScript start at index 0, so heap[0] = 50, heap[1] = 30.

2. Step 2: Identify value at index 1

   heap[1] accesses the second element, which is 30.

3. Final Answer:

   30 -> Option D

4. Quick Check:

   heap[1] = 30 [OK]

Hint: Array index starts at 0, so heap[1] is second element [OK]

Common Mistakes:

• Assuming heap indexing starts at 1
• Confusing value at index 0 with index 1
• Mixing up max-heap property with array indexing

4. Consider this TypeScript snippet to insert a value into a max-heap array:

const heap = [40, 30, 20];
heap.push(50);
// Missing code here to maintain heap property
console.log(heap);

Which code snippet correctly restores the max-heap property after insertion?

medium

A. heap.sort((a, b) => a - b);

B. while (index > 0 && heap[parent(index)] > heap[index]) { swap(heap, parent(index), index); index = parent(index); }

C. while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); }

D. heap.reverse();

Solution

1. Step 1: Understand heapify-up process for max-heap

   After insertion, we compare the inserted node with its parent and swap if child is greater, repeating until heap property is restored.

2. Step 2: Analyze code snippets

   while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); } correctly uses a while loop to swap child and parent if child is greater. while (index > 0 && heap[parent(index)] > heap[index]) { swap(heap, parent(index), index); index = parent(index); } reverses condition (wrong for max-heap). Options A, B, and D do not maintain heap structure.

3. Final Answer:

   while (index > 0 && heap[parent(index)] < heap[index]) { swap(heap, parent(index), index); index = parent(index); } -> Option C

4. Quick Check:

   Heapify-up swaps if child > parent [OK]

Hint: Swap up while child > parent to fix max-heap [OK]

Common Mistakes:

• Using wrong comparison direction in heapify-up
• Sorting array instead of heapifying
• Reversing array instead of fixing heap

5. You have a min-heap represented as an array: [5, 10, 15, 20, 25]. You want to insert 12 and maintain the min-heap property. Which sequence of array states correctly shows the heap after insertion and heapify-up?

hard

A. [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15]

B. [5, 10, 15, 20, 25, 12] -> [5, 10, 15, 20, 25, 12]

C. [5, 10, 15, 20, 25, 12] -> [5, 12, 15, 20, 25, 10]

D. [5, 10, 15, 20, 25, 12] -> [12, 5, 15, 20, 25, 10]

Solution

1. Step 1: Insert 12 at the end of the array

   Initial array after insertion: [5, 10, 15, 20, 25, 12]

2. Step 2: Heapify-up to maintain min-heap

   Compare 12 with its parent 15 (index 2). Since 12 < 15, swap them. New array: [5, 10, 12, 20, 25, 15]. No further swaps needed as 12 > 10.

3. Final Answer:

   [5, 10, 15, 20, 25, 12] -> [5, 10, 12, 20, 25, 15] -> Option A

4. Quick Check:

   Heapify-up swaps child < parent in min-heap [OK]

Hint: Swap inserted value up while smaller than parent in min-heap [OK]

Common Mistakes:

• Not swapping inserted value with parent when smaller
• Assuming no change after insertion
• Swapping with wrong parent index