Heap Insert Operation Bubble Up in DSA Java - Build from Scratch

Heap Insert Operation Bubble Up

📖 Scenario: You are managing a priority queue for a task scheduler. Tasks have priorities represented by numbers. You want to insert a new task into a max-heap so that the highest priority task is always at the top.

🎯 Goal: Build a simple max-heap insert operation that adds a new element to the heap array and then uses the bubble up process to restore the heap property.

📋 What You'll Learn

Create an integer array called heap with initial values {50, 30, 20, 15, 10, 0}

Create an integer variable called size with value 5

Create an integer variable called newValue with value 40

Write a method called bubbleUp that takes the heap array and an index, and moves the element at that index up to restore max-heap order

Insert newValue at the end of heap and increase size by 1

Call bubbleUp with the new element's index

Print the heap array elements from index 0 to size - 1 separated by spaces

💡 Why This Matters

🌍 Real World

Priority queues are used in task scheduling, network routing, and event simulation where the highest priority item must be processed first.

💼 Career

Understanding heap insertions and bubble up operations is essential for software engineers working with efficient data structures and algorithms.

1

Create the initial heap array and size

Create an integer array called heap with values {50, 30, 20, 15, 10, 0} and an integer variable called size with value 5.

DSA Java

// Your code here

Hint

Use int[] heap = {50, 30, 20, 15, 10, 0}; to create the array with extra space and int size = 5; for the size.

2

Add the new value to insert

Create an integer variable called newValue and set it to 40.

DSA Java

int[] heap = {50, 30, 20, 15, 10, 0};
int size = 5;
// Your code here

Hint

Use int newValue = 40; to store the new task priority.

3

Implement bubbleUp method and insert new value

Write a method called bubbleUp that takes int[] heap and int index. It should move the element at index up the heap until the max-heap property is restored. Then add newValue at heap[size], increase size by 1, and call bubbleUp(heap, size - 1).

DSA Java

int[] heap = {50, 30, 20, 15, 10, 0};
int size = 5;
int newValue = 40;

// Your code here

Hint

Use a while loop to compare the current element with its parent and swap if needed. Insert newValue at the end and call bubbleUp.

4

Print the heap after insertion

Use a for loop with variable i from 0 to size - 1 to print each element of heap separated by spaces on one line.

DSA Java

int[] heap = {50, 30, 20, 15, 10, 0};
int size = 5;
int newValue = 40;

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

heap[size] = newValue;
size++;
bubbleUp(heap, size - 1);

// Your code here

Hint

Use a for loop to print elements from index 0 to size - 1 separated by spaces.

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