Heap Insert Operation Bubble Up in DSA Java

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 adding a new kid to a line sorted by height. The kid stands at the end and then moves forward swapping places with taller kids until everyone is in order.

Heap as array:
[10, 15, 20, 17, 25]
Insert 13 at end:
[10, 15, 20, 17, 25, 13]
Index positions:
[0,  1,  2,  3,  4,  5]

Dry Run Walkthrough

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

Goal: Add 13 and restore heap property by moving it up if needed

Step 1: Insert 13 at the end of the array

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

Why: New value must be added at the last position before fixing heap

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

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

Why: Heap is a min-heap, smaller values must be higher, so bubble up 13

Step 3: Now 13 is at index 2; compare with parent 10 at index 0; 13 > 10, stop bubbling

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

Why: Parent is smaller, heap property restored

Result:

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

Annotated Code

DSA Java

public class MinHeap {
    private int[] heap;
    private int size;
    private int capacity;

    public MinHeap(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.heap = new int[capacity];
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private void swap(int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }

    public void insert(int value) {
        if (size == capacity) {
            System.out.println("Heap is full");
            return;
        }
        heap[size] = value; // place at end
        int current = size;
        size++;

        // bubble up
        while (current > 0 && heap[current] < heap[parent(current)]) {
            swap(current, parent(current)); // swap with parent
            current = parent(current); // move up
        }
    }

    public void printHeap() {
        for (int i = 0; i < size; i++) {
            System.out.print(heap[i]);
            if (i < size - 1) System.out.print(" -> ");
        }
        System.out.println(" -> null");
    }

    public static void main(String[] args) {
        MinHeap minHeap = new MinHeap(10);
        int[] initial = {10, 15, 20, 17, 25};
        for (int val : initial) {
            minHeap.insert(val);
        }
        minHeap.insert(13); // insert new value
        minHeap.printHeap();
    }
}

heap[size] = value; // place at end

Insert new value at the end of the heap array

while (current > 0 && heap[current] < heap[parent(current)]) {

Check if current value is smaller than parent to decide if bubble up needed

swap(current, parent(current)); // swap with parent

Swap current node with parent to move smaller value up

current = parent(current); // move up

Update current index to parent's index to continue bubbling up

Output

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

Complexity Analysis

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

Space: O(n) for storing the heap array of n elements

vs Alternative: Compared to inserting and then sorting the entire array O(n log n), bubble up is faster and only fixes heap locally

Edge Cases

Insert into empty heap

Value is placed at root with no bubbling needed

DSA Java

while (current > 0 && heap[current] < heap[parent(current)]) {

Insert value larger than all existing values

Value stays at the end, no swaps occur

DSA Java

while (current > 0 && heap[current] < heap[parent(current)]) {

Heap is full

Insertion is rejected with message

DSA Java

if (size == capacity) {

When to Use This Pattern

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

Common Mistakes

Mistake: Not updating the current index after swapping with parent
Fix: Assign current = parent(current) after swap to continue bubbling up

Mistake: Swapping when the current value is not smaller than parent
Fix: Only swap if current value is less than parent's value to maintain min-heap

Summary

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

Use it when inserting into a min-heap to keep the smallest values near the top.

The key is to swap the new value with its parent repeatedly until it is no longer smaller.

Practice

1. What is the main purpose of the bubble up operation when inserting a new element into a min-heap?

easy

A. To sort all elements in ascending order

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

C. To move the new element up until the heap property is restored

D. To remove the smallest element from the heap

Solution

1. Step 1: Understand the heap property

   In a min-heap, every parent node must be smaller than its children.

2. Step 2: Purpose of bubble up

   When a new element is added at the bottom, bubble up moves it up to restore the heap property.

3. Final Answer:

   To move the new element up until the heap property is restored -> Option C

4. Quick Check:

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

Hint: Bubble up moves new 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 Java code snippets correctly swaps two elements in an array during the bubble up operation?

easy

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

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

C. int temp = arr[i]; arr[i] = arr[parent]; arr[parent] = arr[i];

D. arr[parent] = arr[i]; arr[i] = arr[parent];

Solution

1. Step 1: Identify correct swap logic

   Swapping requires a temporary variable to hold one value to avoid overwriting.

2. Step 2: Check each option

   int temp = arr[parent]; arr[parent] = arr[i]; arr[i] = temp; correctly uses temp to swap arr[parent] and arr[i]. int temp = arr[i]; arr[i] = arr[parent]; arr[parent] = arr[i]; incorrectly sets arr[parent] to the already modified arr[i], causing data loss. Options B and D overwrite without temp, causing errors.

3. Final Answer:

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

4. Quick Check:

   Swap with temp variable = int temp = arr[parent]; arr[parent] = arr[i]; arr[i] = temp; [OK]

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

Common Mistakes:

• Swapping without a temp variable
• Swapping wrong indices
• Overwriting values causing data loss

3. Consider the min-heap represented by the array: [2, 5, 8, 10, 15]. After inserting the value 1 and performing bubble up, what will be the resulting array?

medium

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

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

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

D. ]5 ,51 ,01 ,8 ,2 ,1[

Solution

1. Step 1: Insert 1 at the end

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

2. Step 2: Bubble up 1

   Parent index of 5 is (5-1)/2 = 2. Compare arr[2]=8 with 1. Since 1 < 8, swap. Array: [2, 5, 1, 10, 15, 8]. Now index of 1 is 2.

3. Step 3: Continue bubble up

   Parent index of 2 is (2-1)/2 = 0. Compare arr[0]=2 with 1. Since 1 < 2, swap. Array: [1, 5, 2, 10, 15, 8].

4. Final Answer:

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

5. Quick Check:

   Bubble up swaps until heap property restored [OK]

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

Common Mistakes:

• Not swapping enough times
• Swapping with wrong parent index
• Incorrect parent calculation

4. The following Java method attempts to perform bubble up after inserting a new element into a min-heap. What is the bug?

void bubbleUp(int[] heap, int index) {
  while (index > 0) {
    int parent = (index - 1) / 2;
    if (heap[index] < heap[parent]) {
      int temp = heap[index];
      heap[index] = heap[parent];
      heap[parent] = temp;
      index = parent;
    }
  }
}

medium

A. The index update should be inside the if block

B. The parent calculation is incorrect

C. The loop condition should be index >= 0

D. The swap logic is wrong

Solution

1. Step 1: Analyze loop and index update

   The index is updated to parent every iteration, even if no swap occurs.

2. Step 2: Identify bug effect

   If no swap happens, index still moves up, causing unnecessary checks and possible infinite loop if heap property is already satisfied.

3. Step 3: Correct fix

   Update index = parent only when a swap occurs inside the if block.

4. Final Answer:

   The index update should be inside the if block -> Option A

5. Quick Check:

   Update index only after swap to avoid wrong moves [OK]

Hint: Move index up only when swapping during bubble up [OK]

Common Mistakes:

• Updating index outside swap condition
• Wrong parent index formula
• Incorrect swap logic

5. You have a max-heap represented by the array [20, 15, 18, 10, 12, 17]. You insert the value 19. After performing the bubble up operation, what is the final array?

hard

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

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

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

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

Solution

1. Step 1: Insert 19 at the end

   Array becomes [20, 15, 18, 10, 12, 17, 19]. Index of 19 is 6.

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

   Parent index of 6 is (6-1)/2 = 2. Compare arr[2]=18 with 19. Since 19 > 18, swap. Array: [20, 15, 19, 10, 12, 17, 18]. Now index of 19 is 2.

3. Step 3: Continue bubble up

   Parent index of 2 is (2-1)/2 = 0. Compare arr[0]=20 with 19. Since 19 < 20, stop bubbling up.

4. Final Answer:

   [20, 15, 19, 10, 12, 17, 18] -> Option D

5. Quick Check:

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

Hint: Swap up while child is greater than parent in max-heap [OK]

Common Mistakes:

• Stopping bubble up too early
• Swapping with wrong parent index
• Confusing min-heap and max-heap rules