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 fixed.

Analogy: Imagine adding a new player to a team lineup at the end, then moving them up the ranks if they are better than the players before them.

Heap as array:
Index:  0   1   2   3   4
Value: [10, 15, 20, 17, 25]
New value to insert: 13 at index 5 (end)

Binary tree view:
       10
      /  \
    15    20
   /  \
 17   25
 ↑ new node at bottom right

Dry Run Walkthrough

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

Goal: Insert 13 and move it up until the heap property (parent smaller than children) is restored

Step 1: Insert 13 at the end of the array

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

Why: New value must start at the bottom to keep complete tree shape

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

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

Why: Smaller values must move up to keep min-heap property

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

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

Why: Heap property is restored, no more swaps needed

Result:

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

Annotated Code

DSA C

#include <stdio.h>

#define MAX_SIZE 100

// Swap two integers
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Bubble up operation to restore min-heap property after insert
void bubbleUp(int heap[], int index) {
    while (index > 0) {
        int parent = (index - 1) / 2;
        if (heap[index] < heap[parent]) {
            swap(&heap[index], &heap[parent]); // swap smaller child up
            index = parent; // move index up to parent
        } else {
            break; // heap property restored
        }
    }
}

// Insert value into heap and bubble up
int insert(int heap[], int *size, int value) {
    if (*size >= MAX_SIZE) {
        return -1; // heap full
    }
    heap[*size] = value; // place at end
    bubbleUp(heap, *size); // fix heap
    (*size)++;
    return 0;
}

// Print heap array
void printHeap(int heap[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", heap[i]);
        if (i < size - 1) printf(" -> ");
    }
    printf("\n");
}

int main() {
    int heap[MAX_SIZE] = {10, 15, 20, 17, 25};
    int size = 5;
    int value = 13;

    insert(heap, &size, value);
    printHeap(heap, size);

    return 0;
}

if (heap[index] < heap[parent]) {

compare child with parent to check if bubbling up is needed

swap(&heap[index], &heap[parent]);

swap child and parent to move smaller value up

index = parent;

move index pointer up to continue bubbling if needed

heap[*size] = value;

insert new value at the end of the heap array

bubbleUp(heap, *size);

restore heap property by bubbling up the new value

Output

10 -> 15 -> 13 -> 17 -> 25 -> 20

Complexity Analysis

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

Space: O(1) because the operation modifies the heap in place without extra storage

vs Alternative: Compared to rebuilding the heap from scratch (O(n)), bubbling up is faster for single inserts

Edge Cases

Insert into empty heap

Value is placed at 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[parent])

Heap is full

Insert returns error -1, no change to heap

DSA C

if (*size >= MAX_SIZE) { return -1; }

When to Use This Pattern

When you need to add an element to a heap and keep it ordered, use bubble up to fix the heap from bottom to top.

Common Mistakes

Mistake: Not updating the index after swapping, causing infinite loop or wrong swaps
Fix: After swapping, set index = parent to continue bubbling up correctly

Summary

It adds a new value to the 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 larger than its parent

B. To remove the smallest element from the heap

C. To sort all elements in ascending order

D. To swap the root with the last element

Solution

1. Step 1: Understand heap property

   A max-heap requires each parent to be greater than or equal to its children.

2. Step 2: Purpose of bubble up

   When inserting, bubble up moves the new element up if it is larger than its parent to restore heap property.

3. Final Answer:

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

4. Quick Check:

   Bubble up fixes heap by moving new element up [OK]

Hint: Bubble up moves new element up to fix heap order [OK]

Common Mistakes:

• Thinking bubble up sorts the entire heap
• Confusing bubble up with removing elements
• Assuming bubble up swaps root with last element

2. Which of the following C code snippets correctly performs the bubble up step after inserting a new element at index i in a max-heap array heap?

easy

A. if (heap[i] > heap[i + 1]) swap(heap[i], heap[i + 1]);

B. 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; }

C. for (int j = i; j > 0; j--) { if (heap[j] > heap[j - 1]) swap(heap[j], heap[j - 1]); }

D. 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; }

Solution

1. Step 1: Identify correct bubble up condition

   Bubble up swaps while current element is greater than its parent at index (i-1)/2.

2. Step 2: Check code correctness

   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; } correctly uses a while loop with condition and swaps elements, updating index i to parent.

3. Final Answer:

   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; } -> Option D

4. Quick Check:

   Bubble up uses parent index (i-1)/2 and swaps if child > parent [OK]

Hint: Use parent index (i-1)/2 and swap if child > parent [OK]

Common Mistakes:

• Using < instead of > in condition
• Using for loop instead of while
• Swapping with next element instead of parent

3. Given the max-heap array heap = [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. [45, 30, 50, 10, 20, 40]

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

Solution

1. Step 1: Insert 45 at the end

   Insert 45 at index 5: heap = [50, 30, 40, 10, 20, 45]

2. Step 2: Bubble up 45

   Parent of index 5 is (5-1)/2=2 with value 40. Since 45 > 40, swap them. New heap: [50, 30, 45, 10, 20, 40]

3. Final Answer:

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

4. Quick Check:

   Inserted 45 bubbled up swapping with 40 [OK]

Hint: Insert at end, swap up if bigger than parent [OK]

Common Mistakes:

• Not swapping after insertion
• Swapping with wrong parent index
• Placing 45 at wrong position

4. Consider the following bubble up code snippet for a max-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 error in this code?

medium

A. Parent index calculation is incorrect

B. The loop should start from i = 1 instead of i > 0

C. The comparison operator should be > instead of < to maintain max-heap property

D. Swapping elements is not needed in bubble up

Solution

1. Step 1: Analyze comparison operator

   Bubble up in max-heap swaps when child is greater than parent, so condition should be heap[i] > heap[parent].

2. Step 2: Identify error

   Code uses heap[i] < heap[parent], which is wrong and breaks max-heap property.

3. Final Answer:

   The comparison operator should be > instead of < to maintain max-heap property -> Option C

4. Quick Check:

   Max-heap bubble up swaps if child > parent [OK]

Hint: Use > to compare child and parent in max-heap bubble up [OK]

Common Mistakes:

• Using < instead of > in condition
• Incorrect parent index formula
• Skipping swaps in bubble up

5. You have a max-heap represented as an array: [60, 40, 55, 20, 30, 50]. You insert 65 at the end and perform bubble up. What is the final heap array after bubble up completes?

hard

A. [65, 60, 55, 20, 30, 50, 40]

B. [65, 40, 60, 20, 30, 50, 55]

C. [60, 40, 65, 20, 30, 50, 55]

D. [60, 40, 55, 20, 30, 50, 65]

Solution

1. Step 1: Insert 65 at the end

   Heap becomes [60, 40, 55, 20, 30, 50, 65]. Index of 65 is 6.

2. Step 2: Bubble up 65

   Parent index = (6-1)/2 = 2, value 55. Since 65 > 55, swap: [60, 40, 65, 20, 30, 50, 55].

3. Step 3: Continue bubble up

   New index = 2. Parent index = (2-1)/2 = 0, value 60. Since 65 > 60, swap: [65, 40, 60, 20, 30, 50, 55].

4. Final Answer:

   [65, 60, 55, 20, 30, 50, 40] -> Option A

5. Quick Check:

   Inserted 65 bubbled up swapping with 55 then 60 [OK]

Hint: Bubble up swaps repeatedly until parent is larger [OK]

Common Mistakes:

• Stopping bubble up after one swap
• Swapping with wrong parent index
• Not updating index after swap