Heap Insert Operation Bubble Up in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after inserting 15?

Given a max-heap represented as an array, what is the array after inserting the value 15 and performing bubble up?

DSA Typescript

const heap = [20, 18, 10, 12, 9];
function insert(heap: number[], value: number): number[] {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] >= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
  return heap;
}
const result = insert(heap, 15);
console.log(result);

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

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

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

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

💡 Hint

Remember to bubble up the inserted value until the max-heap property is restored.

The inserted value 15 is added at the end. It swaps with 10 because 15 > 10, resulting in [20, 18, 15, 12, 9, 10]. No further swaps needed.

❓ Predict Output

intermediate

What is the heap array after inserting 5?

Given a max-heap array, what is the array after inserting 5 and performing bubble up?

DSA Typescript

const heap = [30, 20, 15, 10, 8];
function insert(heap: number[], value: number[]): number[] {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] >= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
  return heap;
}
const result = insert(heap, 5);
console.log(result);

A [30, 20, 15, 10, 8, 5]

B [30, 20, 5, 10, 8, 15]

C [30, 20, 15, 5, 8, 10]

D [30, 20, 15, 10, 5, 8]

💡 Hint

If the inserted value is smaller than its parent, no swaps occur.

5 is added at the end and is smaller than its parent 15, so no bubble up happens. The heap remains [30, 20, 15, 10, 8, 5].

🔧 Debug

advanced

Why does this bubble up code cause an infinite loop?

Identify the bug causing an infinite loop in this bubble up implementation for a max-heap insert.

DSA Typescript

function bubbleUp(heap: number[], index: number): void {
  while (index > 0) {
    let parentIndex = Math.floor(index / 2);
    if (heap[parentIndex] >= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
}
const heap = [50, 30, 40, 10, 20];
bubbleUp(heap, 4);
console.log(heap);

A The function should return the heap array after bubble up

B The swap syntax is incorrect; should use a temp variable

C The loop condition should be index >= 0 instead of index > 0

D parentIndex calculation is wrong; should be Math.floor((index - 1) / 2)

💡 Hint

Check how parent index is calculated for zero-based arrays.

Using Math.floor(index / 2) causes wrong parent index calculation, leading to infinite loop because index may not decrease properly. Correct formula is Math.floor((index - 1) / 2).

❓ Predict Output

advanced

What is the heap array after inserting 25?

Given a max-heap array, what is the array after inserting 25 and performing bubble up?

DSA Typescript

const heap = [40, 30, 20, 10, 15, 5];
function insert(heap: number[], value: number): number[] {
  heap.push(value);
  let index = heap.length - 1;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] >= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
  }
  return heap;
}
const result = insert(heap, 25);
console.log(result);

A [40, 30, 25, 10, 15, 5, 20, 25]

B [40, 30, 20, 10, 15, 5, 25]

C [40, 30, 25, 10, 15, 5, 20]

D [40, 30, 20, 10, 15, 25, 5]

💡 Hint

Bubble up swaps inserted value with parents until heap property is restored.

25 is inserted at the end, swaps with 20 because 25 > 20, resulting in [40, 30, 25, 10, 15, 5, 20]. No further swaps needed.

🧠 Conceptual

expert

How many swaps occur when inserting 100 into this max-heap?

Given the max-heap array [90, 70, 80, 40, 50, 60, 30], how many swaps happen when inserting 100 and performing bubble up?

DSA Typescript

const heap = [90, 70, 80, 40, 50, 60, 30];
function insert(heap: number[], value: number): number[] {
  heap.push(value);
  let index = heap.length - 1;
  let swaps = 0;
  while (index > 0) {
    let parentIndex = Math.floor((index - 1) / 2);
    if (heap[parentIndex] >= heap[index]) break;
    [heap[parentIndex], heap[index]] = [heap[index], heap[parentIndex]];
    index = parentIndex;
    swaps++;
  }
  return heap;
}
const result = insert(heap, 100);
console.log(result);

A 2

B 3

C 4

D 1

💡 Hint

Count how many times the inserted value swaps with its parent until it reaches the root or no longer bigger.

100 swaps with 30 (1), then 80 (2), then 90 (3) and stops at root. Total swaps = 3.

Practice

1. What is the main purpose of the bubble up operation during a heap insert?

easy

A. To swap all elements randomly in the heap

B. To remove the root element from the heap

C. To sort all elements in the heap in ascending order

D. To restore the heap property by moving the new element up if it is smaller (min-heap) or larger (max-heap) than its parent

Solution

1. Step 1: Understand the heap property

   In a min-heap, each parent node must be smaller than its children. In a max-heap, each parent must be larger.

2. Step 2: Purpose of bubble up

   When inserting a new element, it is placed at the end. Bubble up moves it up the tree to restore the heap property if violated.

3. Final Answer:

   To restore the heap property by moving the new element up if it is smaller (min-heap) or larger (max-heap) than its parent -> Option D

4. Quick Check:

   Bubble up fixes heap order after insert [OK]

Hint: Bubble up fixes heap order by moving new element up [OK]

Common Mistakes:

• Confusing bubble up with removing elements
• Thinking bubble up sorts the entire heap
• Assuming bubble up swaps elements randomly

2. Which of the following TypeScript code snippets correctly performs the bubble up step in a min-heap after inserting a new element at the end?

easy

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

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

C. for (let i = 0; i < heap.length; i++) { if (heap[i] < heap[i+1]) swap(heap, i, i+1); }

D. if (heap[index] > heap[parentIndex]) { swap(heap, index, parentIndex); }

Solution

1. Step 1: Identify min-heap bubble up condition

   In a min-heap, bubble up swaps while the child is smaller than the parent.

2. Step 2: Check code correctness

   while (index > 0 && heap[index] < heap[parentIndex]) { swap(heap, index, parentIndex); index = parentIndex; } uses a while loop with condition heap[index] < heap[parentIndex], correctly swapping and updating index.

3. Final Answer:

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

4. Quick Check:

   Min-heap bubble up swaps smaller child up [OK]

Hint: Bubble up swaps while child < parent in min-heap [OK]

Common Mistakes:

• Using > instead of < for min-heap
• Using for loop instead of while
• Not updating index after swap

3. Given a max-heap represented as an array: [50, 30, 40, 10, 20], what will be the heap array after inserting 45 and performing bubble up?

medium

A. [50, 45, 40, 10, 20, 30]

B. [50, 30, 45, 10, 20, 40]

C. [50, 30, 40, 10, 20, 45]

D. [45, 30, 50, 10, 20, 40]

Solution

1. Step 1: Insert 45 at the end

   Array becomes [50, 30, 40, 10, 20, 45]

2. Step 2: Bubble up 45 in max-heap

   Parent index of 45 (index 5) is 2 (value 40). Since 45 > 40, swap. New array: [50, 30, 45, 10, 20, 40]. Now index 2's parent is 0 (value 50). 45 < 50, stop bubbling up.

3. Final Answer:

   [50, 30, 45, 10, 20, 40] -> Option B

4. Quick Check:

   Bubble up swaps 45 with 40 only [OK]

Hint: Insert at end, swap up while child > parent in max-heap [OK]

Common Mistakes:

• Not swapping 45 with 40
• Swapping 45 with 30 instead of 40
• Stopping bubble up too early

4. Consider this bubble up code snippet for a min-heap insert:

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

What is the error in this code?

medium

A. The parentIndex is not updated inside the loop

B. The swap function is called incorrectly

C. The comparison operator should be '<' to maintain min-heap property

D. The loop should run while index < 0

Solution

1. Step 1: Check comparison for min-heap bubble up

   In a min-heap, bubble up swaps when child is smaller than parent, so condition should be heap[index] < heap[parentIndex].

2. Step 2: Identify error in code

   The code uses '>' which is incorrect for min-heap bubble up, causing wrong swaps.

3. Final Answer:

   The comparison operator should be '<' to maintain min-heap property -> Option C

4. Quick Check:

   Min-heap bubble up uses < comparison [OK]

Hint: Min-heap bubble up swaps when child < parent [OK]

Common Mistakes:

• Using > instead of < in condition
• Not updating parentIndex after swap
• Loop condition index > 0 is correct, not < 0

5. You have a min-heap represented as [5, 10, 15, 20, 25, 30]. You insert 12 and perform bubble up. After that, you insert 3 and perform bubble up again. What is the final heap array?

hard

A. [3, 5, 12, 10, 25, 30, 15, 20]

B. [3, 5, 15, 10, 25, 30, 12, 20]

C. [3, 5, 12, 20, 25, 30, 15, 10]

D. [3, 5, 15, 20, 25, 30, 12, 10]

Solution

1. Step 1: Insert 12 and bubble up

   Insert 12 at index 6: [5,10,15,20,25,30,12]. Parent of index 6 is 2 (value 15). Since 12 < 15, swap: [5,10,12,20,25,30,15]. Parent of index 2 is 0 (value 5). 12 > 5, stop.

2. Step 2: Insert 3 and bubble up

   Insert 3 at index 7: [5,10,12,20,25,30,15,3]. Parent of index 7 is 3 (value 20). 3 < 20, swap: [5,10,12,3,25,30,15,20]. Parent of index 3 is 1 (value 10). 3 < 10, swap: [5,3,12,10,25,30,15,20]. Parent of index 1 is 0 (value 5). 3 < 5, swap: [3,5,12,10,25,30,15,20]. Now at root, stop.

3. Final Answer:

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

4. Quick Check:

   Bubble up swaps until heap property restored [OK]

Hint: Bubble up each insert until parent smaller in min-heap [OK]

Common Mistakes:

• Not swapping 3 all the way to root
• Incorrect parent index calculation
• Stopping bubble up too early