Heap Insert Operation Bubble Up in DSA Typescript - Execution Trace

Concept Flow - Heap Insert Operation Bubble Up

Add new element at end of array

↓

Compare new element with parent

↓

Swap with parent

↓

Move pointer to parent

↩Back to Compare

Insert element at the end, then compare and swap with parent until heap property is restored.

Execution Sample

DSA Typescript

heap = [10, 15, 30, 40, 50, 100, 40]
insert(8)
// Bubble up to restore heap

Insert 8 into min-heap and bubble it up to maintain heap order.

Execution Table

Step	Operation	Array State	Pointer (index)	Action	Visual State
1	Insert 8 at end	[10, 15, 30, 40, 50, 100, 40, 8]	7 (new element)	Add 8 at index 7	Array: [10, 15, 30, 40, 50, 100, 40, 8]
2	Compare with parent	[10, 15, 30, 40, 50, 100, 40, 8]	7 (8) vs 3 (40)	8 < 40 → Swap	Swap index 7 and 3
3	After swap	[10, 15, 30, 8, 50, 100, 40, 40]	3 (8)	Move pointer to 3	Array: [10, 15, 30, 8, 50, 100, 40, 40]
4	Compare with parent	[10, 15, 30, 8, 50, 100, 40, 40]	3 (8) vs 1 (15)	8 < 15 → Swap	Swap index 3 and 1
5	After swap	[10, 8, 30, 15, 50, 100, 40, 40]	1 (8)	Move pointer to 1	Array: [10, 8, 30, 15, 50, 100, 40, 40]
6	Compare with parent	[10, 8, 30, 15, 50, 100, 40, 40]	1 (8) vs 0 (10)	8 < 10 → Swap	Swap index 1 and 0
7	After swap	[8, 10, 30, 15, 50, 100, 40, 40]	0 (8)	Move pointer to 0	Array: [8, 10, 30, 15, 50, 100, 40, 40]
8	Compare with parent	[8, 10, 30, 15, 50, 100, 40, 40]	0 (8) has no parent	Stop bubbling up	Heap property restored

💡 Pointer reached root (index 0), no parent to compare, bubble up stops.

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	Final
heap array	[10, 15, 30, 40, 50, 100, 40]	[10, 15, 30, 40, 50, 100, 40, 8]	[10, 15, 30, 8, 50, 100, 40, 40]	[10, 8, 30, 15, 50, 100, 40, 40]	[8, 10, 30, 15, 50, 100, 40, 40]	[8, 10, 30, 15, 50, 100, 40, 40]
pointer index	N/A	7	3	1	0	0
pointer value	N/A	8	8	8	8	8

Key Moments - 3 Insights

Why do we compare the new element with its parent during bubble up?

Because the heap property depends on parent-child order. We check if the new element is smaller than its parent to decide if swapping is needed (see execution_table steps 2, 4, 6).

What happens when the pointer reaches the root during bubble up?

There is no parent to compare with, so the bubble up stops (see execution_table step 8). This means the heap property is restored.

Why do we swap elements during bubble up instead of just inserting at the end?

Inserting at the end may break the heap order. Swapping with parents moves the new element up to restore the heap property (see execution_table steps 2, 4, 6).

Visual Quiz - 3 Questions

Look at the execution table, what is the heap array after step 5?

A [10, 8, 30, 15, 50, 100, 40, 40]

B [10, 15, 30, 8, 50, 100, 40, 40]

C [8, 10, 30, 15, 50, 100, 40, 40]

D [10, 15, 30, 40, 50, 100, 40, 8]

💡 Hint

Check the 'Array State' column at step 5 in the execution_table.

At which step does the pointer reach the root and stop bubbling up?

A Step 6

B Step 8

C Step 7

D Step 5

💡 Hint

Look for the step where the pointer index is 0 and no parent exists in execution_table.

If the inserted element was 50 instead of 8, how would the bubble up process change?

A It would bubble up to the root.

B It would swap once with the parent.

C No swaps would happen; insertion stops immediately.

D It would cause an error.

💡 Hint

Refer to the comparison logic in execution_table steps 2, 4, 6 where swaps happen only if new element is less than parent.

Concept Snapshot

Heap Insert Bubble Up:
- Insert new element at array end
- Compare with parent node
- If new < parent, swap
- Move pointer to parent
- Repeat until root or no swap needed
- Restores heap property efficiently

Full Transcript

This visual trace shows how inserting a new element into a min-heap works by adding it at the end of the array and then bubbling it up. The bubble up compares the new element with its parent and swaps if the new element is smaller. This process repeats until the new element reaches the root or no swap is needed, restoring the heap property. The execution table tracks each step, showing array states and pointer movements. Key moments clarify why comparisons and swaps happen and when the process stops. The quiz tests understanding of array states and stopping conditions.

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