Heap insertion (bubble up) in Data Structures Theory - Step-by-Step Execution

Concept Flow - Heap insertion (bubble up)

Insert new element at end of array

↓

Compare new element with parent

↓

Swap with parent

↓

Move pointer to parent

↩Back to Compare

The new element is added at the end, then repeatedly compared with its parent. If smaller, it swaps and moves up until heap property is restored.

Execution Sample

Data Structures Theory

Array: [10, 15, 30, 40, 50, 100, 40]
Insert: 8
Steps: Add 8 at end, compare with parent, swap if smaller, repeat

This shows inserting 8 into a min-heap and bubbling it up to restore heap order.

Analysis Table

Step	Operation	Array State	Parent Index	Compare (Child < Parent?)	Swap?	Resulting Array
1	Insert 8 at end	[10, 15, 30, 40, 50, 100, 40, 8]	3	8 < 40? Yes	Yes	[10, 15, 30, 8, 50, 100, 40, 40]
2	Move to parent index 3	[10, 15, 30, 8, 50, 100, 40, 40]	1	8 < 15? Yes	Yes	[10, 8, 30, 15, 50, 100, 40, 40]
3	Move to parent index 1	[10, 8, 30, 15, 50, 100, 40, 40]	0	8 < 10? Yes	Yes	[8, 10, 30, 15, 50, 100, 40, 40]
4	Move to parent index 0	[8, 10, 30, 15, 50, 100, 40, 40]	-	No parent (root)	No	[8, 10, 30, 15, 50, 100, 40, 40]

💡 Reached root node, no parent to compare, bubble up stops.

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
Array	[10, 15, 30, 40, 50, 100, 40]	[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]
Child Index	-	7	3	1	0
Parent Index	-	3	1	0	-

Key Insights - 3 Insights

Why do we insert the new element at the end of the array first?

Inserting at the end keeps the complete binary tree structure intact before fixing heap order by bubbling up, as shown in Step 1 of the execution_table.

Why do we stop bubbling up when we reach the root?

The root has no parent to compare with, so no further swaps are possible. This is shown in Step 4 where parent index is '-' and bubble up stops.

What happens if the new element is not smaller than its parent?

No swap occurs and bubbling up stops immediately, preserving heap order. This is the 'Not less' branch in the concept_flow.

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after Step 2?

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

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

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

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

💡 Hint

Check the 'Resulting Array' column for Step 2 in the execution_table.

At which step does the bubble up process stop?

A Step 2

B Step 3

C Step 4

D Step 1

💡 Hint

Look for the step where parent index is '-' and no swap occurs in the execution_table.

If the inserted element was 35 instead of 8, how would the first comparison (Step 1) change?

A 35 < 40? Yes, swap occurs

B 35 < 40? No, no swap

C 35 < 30? Yes, swap occurs

D 35 < 30? No, no swap

💡 Hint

Refer to the 'Compare' column in Step 1 and consider the inserted value compared to its parent.

Concept Snapshot

Heap insertion (bubble up):
- Insert new element at array end (maintains complete tree)
- Compare with parent: if smaller, swap
- Move pointer to parent and repeat
- Stop when root reached or no swap needed
- Restores min-heap property efficiently

Full Transcript

Heap insertion with bubble up means adding the new element at the end of the heap array to keep the tree complete. Then, we compare this new element with its parent. If the new element is smaller, we swap them and move up to the parent's position. This process repeats until the new element is no longer smaller than its parent or it reaches the root. The execution table shows each step with array states and comparisons. Key points include why insertion is at the end, why bubbling stops at the root, and what happens if no swap is needed. The visual quiz tests understanding of array states and stopping conditions.

Practice

1. What is the first step when inserting a new element into a binary heap using the bubble up method?

easy

A. Add the new element at the end of the heap

B. Compare the new element with the root

C. Remove the smallest element

D. Sort all elements in the heap

Solution

1. Step 1: Add new element at the end

   The new element is always added at the end of the heap to maintain the complete tree property.

2. Step 2: Prepare for bubble up

   After adding, the element will be compared with its parent to restore heap order.

3. Final Answer:

   Add the new element at the end of the heap -> Option A

4. Quick Check:

   Insertion starts by adding at the end [OK]

Hint: New elements always start at the end before bubbling up [OK]

Common Mistakes:

• Starting at the root instead of the end
• Removing elements before insertion
• Sorting the entire heap immediately

2. Which of the following correctly describes the condition to continue bubbling up in a min-heap after insertion?

easy

A. Never bubble up after insertion

B. Continue bubbling up if the new element is greater than its parent

C. Continue bubbling up if the new element is equal to its parent

D. Continue bubbling up if the new element is less than its parent

Solution

1. Step 1: Understand min-heap property

   In a min-heap, parents must be less than or equal to their children.

2. Step 2: Bubble up condition

   If the new element is less than its parent, it violates the heap property and must bubble up.

3. Final Answer:

   Continue bubbling up if the new element is less than its parent -> Option D

4. Quick Check:

   Bubble up when child < parent in min-heap [OK]

Hint: Bubble up when new element is smaller than parent in min-heap [OK]

Common Mistakes:

• Bubbling up when new element is greater
• Ignoring equality cases
• Not bubbling up at all

3. Given a min-heap represented as an array: [2, 5, 8, 10, 15], what will be the array after inserting 1 and performing bubble up?

medium

A. [1, 2, 8, 10, 15, 5]

B. [1, 2, 5, 10, 15, 8]

C. [1, 5, 2, 10, 15, 8]

D. [2, 5, 8, 10, 15, 1]

Solution

1. Step 1: Insert 1 at the end

   Array becomes [2, 5, 8, 10, 15, 1].

2. Step 2: Bubble up 1

   Compare 1 with parent 8 (index 2). Since 1 < 8, swap: [2, 5, 1, 10, 15, 8]. Then compare 1 with parent 5 (index 1). Since 1 < 5, swap: [2, 1, 8, 10, 15, 5]. Then compare 1 with parent 2 (index 0). Since 1 < 2, swap: [1, 2, 8, 10, 15, 5].

3. Final Answer:

   [1, 2, 5, 10, 15, 8] -> Option B

4. Quick Check:

   Bubble up swaps until heap property restored [OK]

Hint: Insert at end, then swap up while smaller than parent [OK]

Common Mistakes:

• Not swapping enough times
• Swapping with wrong parent
• Leaving new element at the end

4. Consider the following code snippet for inserting into a min-heap. What is the error?

def bubble_up(heap, index):
    while index > 0:
        parent = (index - 1) // 2
        if heap[index] > heap[parent]:
            heap[index], heap[parent] = heap[parent], heap[index]
            index = parent
        else:
            break

medium

A. The comparison should be heap[index] < heap[parent] for min-heap

B. The parent index calculation is incorrect

C. The loop condition should be index >= 0

D. Swapping should happen only if heap[index] == heap[parent]

Solution

1. Step 1: Analyze comparison logic

   For a min-heap, bubble up should swap when child is less than parent, not greater.

2. Step 2: Identify correct condition

   The code uses '>' which is wrong; it should be '<' to maintain min-heap property.

3. Final Answer:

   The comparison should be heap[index] < heap[parent] for min-heap -> Option A

4. Quick Check:

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

Hint: Use < comparison for min-heap bubble up [OK]

Common Mistakes:

• Using > instead of <
• Wrong parent index formula
• Incorrect loop condition

5. You have a max-heap represented as [20, 15, 18, 8, 10, 17]. You insert 19. After bubble up, what is the correct heap array?

hard

A. [20, 15, 18, 8, 10, 17, 19]

B. [20, 19, 18, 8, 10, 17, 15]

C. [20, 15, 19, 8, 10, 17, 18]

D. [20, 19, 18, 15, 10, 17, 8]

Solution

1. Step 1: Insert 19 at the end

   Array becomes [20, 15, 18, 8, 10, 17, 19].

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

   Parent of index 6 is index 2 (value 18). Since 19 > 18, swap: [20, 15, 19, 8, 10, 17, 18]. Next parent is index 0 (value 20). Since 19 < 20, stop bubbling up.

3. Step 3: Final heap array

   The final array is [20, 15, 19, 8, 10, 17, 18].

4. Final Answer:

   [20, 15, 19, 8, 10, 17, 18] -> Option C

5. Quick Check:

   Bubble up swaps child > parent in max-heap [OK]

Hint: In max-heap, bubble up while child is greater than parent [OK]

Common Mistakes:

• Not swapping enough times
• Swapping with wrong parent
• Leaving new element at the end