Heap Insert Operation Bubble Up in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to get the parent index of a node in a heap.

DSA Typescript

const parentIndex = (index: number) => Math.floor((index [1] 1) / 2);

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of - causes wrong parent calculation.

Using * or / instead of - leads to incorrect index.

To find the parent index in a heap, subtract 1 from the current index before dividing by 2.

2fill in blank

medium

Complete the code to swap two elements in the heap array.

DSA Typescript

const swap = (arr: number[], i: number, j: number) => { const temp = arr[i]; arr[i] = arr[[1]]; arr[[1]] = temp; };

Drag options to blanks, or click blank then click option'

Aarr.length

Bi

C0

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping arr[i] with arr[i] does nothing.

Using 0 or arr.length as index causes errors.

To swap elements, assign arr[i] to arr[j] and arr[j] to temp.

3fill in blank

hard

Fix the error in the bubble up loop condition to continue while the current node is smaller than its parent.

DSA Typescript

let parent = Math.floor((index - 1) / 2);
while (index > 0 && heap[index] [1] heap[parent]) {
  swap(heap, index, parent);
  index = parent;
  parent = Math.floor((index - 1) / 2);
}

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' reverses the heap property.

Using '==' or '!=' causes infinite or no swaps.

In a min-heap, bubble up continues while current node is less than its parent.

4fill in blank

hard

Fill both blanks to complete the bubble up function that inserts a value and restores heap order.

DSA Typescript

function bubbleUp(heap: number[], value: number) {
  heap.push(value);
  let index = heap.length [1] 1;
  while (index > 0) {
    const parent = Math.floor((index [2] 1) / 2);
    if (heap[index] >= heap[parent]) break;
    swap(heap, index, parent);
    index = parent;
  }
}

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of - causes wrong indices.

Using * or / breaks the parent calculation.

Index starts at last element (length - 1). Parent index uses (index - 1) / 2.

5fill in blank

hard

Fill all three blanks to complete the bubble up logic with correct conditions and swapping.

DSA Typescript

function bubbleUp(heap: number[], value: number) {
  heap.push(value);
  let index = heap.length [1] 1;
  while (index > 0) {
    const parent = Math.floor((index [2] 1) / 2);
    if (heap[index] [3] heap[parent]) break;
    swap(heap, index, parent);
    index = parent;
  }
}

Drag options to blanks, or click blank then click option'

A-

B>=

C<

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of - for indices.

Using '<' or '!=' in break condition causes wrong loop behavior.

Index starts at length - 1; parent uses (index - 1)/2; break if current node >= parent.

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