Heap Insert Operation Bubble Up in DSA C#

Mental Model

When adding a new number to a heap, we put it at the end and then move it up until the heap rules are right again.

Analogy: Imagine a new player joining a line based on height. They start at the back and move forward until they stand in the right spot by height order.

Heap as array:
[10, 15, 20, 17, 25]
Insert 13 at end:
[10, 15, 20, 17, 25, 13]
Positions:
Index: 0   1   2   3   4   5
Value:10 ->15 ->20 ->17 ->25 ->13
                  ↑ new

Dry Run Walkthrough

Input: heap: [10, 15, 20, 17, 25], insert value 13

Goal: Add 13 and move it up until the heap property (parent ≤ children) is restored

Step 1: Insert 13 at the end of the heap array

[10, 15, 20, 17, 25, 13]

Why: New value must start at the last position before moving up

Step 2: Compare 13 with its parent 20; since 13 < 20, swap them

[10, 15, 13, 17, 25, 20]

Why: Heap rule broken, smaller child must move up

Step 3: Compare 13 with new parent 15; since 13 < 15, swap them

[10, 13, 15, 17, 25, 20]

Why: Heap rule broken, smaller child must move up

Step 4: Compare 13 with new parent 10; since 13 > 10, stop bubbling up

[10, 13, 15, 17, 25, 20]

Why: Heap property restored, no more swaps needed

Result:

[10, 13, 15, 17, 25, 20]

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class MinHeap
{
    private List<int> heap = new List<int>();

    public void Insert(int val)
    {
        heap.Add(val); // add at end
        BubbleUp(heap.Count - 1); // fix heap property
    }

    private void BubbleUp(int index)
    {
        while (index > 0)
        {
            int parentIndex = (index - 1) / 2;
            if (heap[index] < heap[parentIndex])
            {
                // swap child and parent
                int temp = heap[index];
                heap[index] = heap[parentIndex];
                heap[parentIndex] = temp;

                index = parentIndex; // move up
            }
            else
            {
                break; // heap property restored
            }
        }
    }

    public void PrintHeap()
    {
        Console.WriteLine(string.Join(", ", heap));
    }
}

class Program
{
    static void Main()
    {
        MinHeap heap = new MinHeap();
        int[] initial = {10, 15, 20, 17, 25};
        foreach (int val in initial)
        {
            heap.Insert(val);
        }
        heap.Insert(13); // insert new value
        heap.PrintHeap();
    }
}

heap.Add(val); // add at end

Add new value at the end of the heap array

BubbleUp(heap.Count - 1); // fix heap property

Start bubbling up from the last index

int parentIndex = (index - 1) / 2;

Calculate parent index of current node

if (heap[index] < heap[parentIndex])

Check if child is smaller than parent to decide swap

swap child and parent

Swap to move smaller value up

index = parentIndex; // move up

Update index to parent's position to continue bubbling

else break; // heap property restored

Stop bubbling when heap property is satisfied

Output

10, 13, 15, 17, 25, 20

Complexity Analysis

Time: O(log n) because in worst case the new element moves up the height of the heap, which is log n

Space: O(n) because the heap stores all elements in a list

vs Alternative: Compared to inserting and then rebuilding the heap from scratch (O(n)), bubbling up is more efficient for single inserts

Edge Cases

Insert into empty heap

Value is added as root with no bubbling needed

DSA C#

while (index > 0)

Insert value larger than all existing values

Value stays at the end, no swaps occur

DSA C#

if (heap[index] < heap[parentIndex])

Insert duplicate value equal to parent

No swap since child is not smaller, bubbling stops

DSA C#

if (heap[index] < heap[parentIndex])

When to Use This Pattern

When you need to add a new element to a heap and keep it ordered, use bubble up to restore heap order efficiently.

Common Mistakes

Mistake: Not updating the index after swapping during bubble up
Fix: Set index = parentIndex after swap to continue bubbling up

Mistake: Swapping when child is not smaller than parent in a min-heap
Fix: Only swap if child is strictly smaller than parent

Summary

It adds a new value to a heap and moves it up until the heap order is correct.

Use it when inserting elements into a min-heap to keep the smallest value at the top.

The key is to swap the new value with its parent while it is smaller, moving it up step by step.

Practice

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

easy

A. To restore the heap property by moving the new element up if it is smaller than its parent

B. To move the new element to the bottom of the heap

C. To remove the smallest element from the heap

D. To sort all elements in the heap

Solution

1. Step 1: Understand heap property

   In a min-heap, every parent node is smaller than its children. When inserting, this property might break.

2. Step 2: Purpose of bubble up

   The bubble up operation moves the newly inserted element up the tree if it is smaller than its parent, restoring the heap property.

3. Final Answer:

   To restore the heap property by moving the new element up if it is smaller than its parent -> Option A

4. Quick Check:

   Bubble up fixes heap order by moving smaller elements up [OK]

Hint: Bubble up moves smaller inserted element up to fix heap [OK]

Common Mistakes:

• Thinking bubble up moves element down
• Confusing bubble up with removing elements
• Assuming bubble up sorts the entire heap

2. Which of the following C# code snippets correctly swaps two elements in an array during bubble up?

easy

A. int temp = heap[parent]; heap[parent] = heap[i]; heap[i] = temp;

B. heap[i] = heap[parent]; heap[parent] = heap[i];

C. heap[i] = heap[parent]; heap[parent] = heap[parent];

D. int temp = heap[i]; heap[i] = heap[parent]; heap[parent] = heap[i];

Solution

1. Step 1: Understand swapping logic

   To swap two elements, store one in a temporary variable, assign the second to the first, then assign temp to the second.

2. Step 2: Check each option

   int temp = heap[parent]; heap[parent] = heap[i]; heap[i] = temp; correctly stores heap[parent] in temp, then swaps heap[parent] and heap[i]. int temp = heap[i]; heap[i] = heap[parent]; heap[parent] = heap[i]; swaps incorrectly by storing heap[i] first.

3. Final Answer:

   int temp = heap[parent]; heap[parent] = heap[i]; heap[i] = temp; -> Option A

4. Quick Check:

   Swap uses temp variable correctly [OK]

Hint: Use temp variable to swap two array elements safely [OK]

Common Mistakes:

• Overwriting one element before saving it
• Swapping without temp variable causing data loss
• Confusing indices in swap

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

medium

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

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

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

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

Solution

1. Step 1: Insert 1 at the end

   Insert 1 at index 5: [2, 5, 8, 10, 15, 1]

2. Step 2: Bubble up 1

   Parent of index 5 is index 2 (value 8). Since 1 < 8, swap: [2, 5, 1, 10, 15, 8]. Now index 2's parent is index 0 (value 2). Since 1 < 2, swap again: [1, 5, 2, 10, 15, 8].

3. Final Answer:

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

4. Quick Check:

   Bubble up swaps until heap property restored [OK]

Hint: Insert at end, swap with parent while smaller [OK]

Common Mistakes:

• Not swapping enough times to restore heap
• Swapping with wrong parent index
• Inserting element at wrong position

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

while (i > 0 && heap[i] < heap[(i - 1) / 2]) {
    int temp = heap[i];
    heap[i] = heap[(i - 1) / 2];
    heap[(i - 1) / 2] = temp;
    i = (i - 1) / 2;
}

What is the bug in this code?

medium

A. The parent index calculation is incorrect; it should be (i / 2) instead of (i - 1) / 2

B. No bug; the code correctly performs bubble up

C. The swap uses wrong indices; should swap with i + 1

D. The loop condition should use > instead of < for a min-heap

Solution

1. Step 1: Check parent index formula

   Parent index in zero-based heap is (i - 1) / 2, which is correct.

2. Step 2: Check loop condition and swap

   Loop continues while current element is smaller than parent, swapping them correctly. Indices used in swap are correct.

3. Final Answer:

   No bug; the code correctly performs bubble up -> Option B

4. Quick Check:

   Parent index and swap logic are correct [OK]

Hint: Parent index = (i-1)/2; swap if child smaller [OK]

Common Mistakes:

• Using wrong parent index formula
• Reversing comparison operator in condition
• Swapping with wrong indices

5. You have a max-heap represented by the array [20, 15, 18, 8, 10, 5]. You insert 17 and perform bubble up. What is the final heap array?

hard

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

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

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

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

Solution

1. Step 1: Insert 17 at the end

   Insert 17 at index 6: [20, 15, 18, 8, 10, 5, 17]

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

   Parent of index 6 is index 2 (value 18). Since 17 < 18, no swap needed. Heap remains [20, 15, 18, 8, 10, 5, 17].

3. Step 3: Verify parent index

   Parent of 6 is (6-1)/2 = 2 (18). 17 < 18, so no swap for max-heap bubble up.

4. Step 4: Re-examine options

   Options A and B show incorrect bubbling up (A swaps with wrong parent 15, B swaps with parent 18). Since 17 < 18, no swap. Heap stays [20, 15, 18, 8, 10, 5, 17] matching [20, 15, 18, 8, 10, 5, 17].

5. Final Answer:

   [20, 15, 18, 8, 10, 5, 17] -> Option D

6. Quick Check:

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

Hint: In max-heap, bubble up if child > parent only [OK]

Common Mistakes:

• Swapping when child is smaller than parent
• Confusing max-heap with min-heap rules
• Incorrect parent index calculation