Heap Insert Operation Bubble Up in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after inserting 15?

Given a max-heap represented as an array, what is the array after inserting the value 15 and performing bubble up?

DSA Java

int[] heap = {20, 18, 10, 12, 9, 8};
// Insert 15 and bubble up
// Show final heap array

A [20, 18, 10, 12, 9, 8, 15]

B [20, 18, 10, 15, 9, 8, 12]

C [20, 18, 15, 12, 9, 10, 8]

D [20, 18, 15, 12, 9, 8, 10]

💡 Hint

Remember to bubble up the inserted element until the max-heap property is restored.

After inserting 15 at the end, it bubbles up swapping with 10 to maintain max-heap property. Final array is [20, 18, 15, 12, 9, 8, 10].

❓ Predict Output

intermediate

What is the heap array after inserting 5?

Given a max-heap array, what is the array after inserting 5 and performing bubble up?

DSA Java

int[] heap = {30, 20, 15, 10, 8, 12};
// Insert 5 and bubble up
// Show final heap array

A [30, 20, 15, 10, 8, 5, 12]

B [30, 20, 15, 10, 8, 12, 5]

C [30, 20, 15, 10, 5, 8, 12]

D [30, 20, 15, 5, 8, 12, 10]

💡 Hint

If the inserted value is smaller than its parent, no bubble up occurs.

5 is inserted at the end. Its parent is 15 which is larger, so no swaps happen. Final array is [30, 20, 15, 10, 8, 12, 5].

🔧 Debug

advanced

Why does this bubble up code cause an infinite loop?

Consider this bubble up code snippet for a max-heap insert. Why does it cause an infinite loop?

DSA Java

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

A The parent index calculation is incorrect and causes index out of bounds error.

B The comparison operator should be < instead of > causing wrong loop condition.

C Variable i is never updated inside the loop, so condition never changes causing infinite loop.

D The swap logic is wrong and swaps wrong elements causing infinite loop.

💡 Hint

Check if the loop variable changes inside the loop.

The variable i is never updated inside the while loop, so the condition remains true forever causing infinite loop.

❓ Predict Output

advanced

What is the heap array after inserting 25?

Given a max-heap array, what is the array after inserting 25 and performing bubble up?

DSA Java

int[] heap = {40, 30, 20, 15, 10, 18};
// Insert 25 and bubble up
// Show final heap array

A [40, 30, 25, 15, 10, 18, 20]

B [40, 30, 20, 25, 10, 18, 15]

C [40, 30, 25, 20, 10, 18, 15]

D [40, 30, 20, 15, 25, 18, 10]

💡 Hint

Bubble up swaps with parent if inserted value is larger.

Insert 25 at index 6. Parent index is 2 with value 20. 25 > 20, swap. Result: [40, 30, 25, 15, 10, 18, 20]. No further swaps needed.

🧠 Conceptual

expert

What is the time complexity of the bubble up operation in a heap insert?

Choose the correct time complexity for the bubble up operation when inserting an element into a heap of size n.

A O(log n) because the element may bubble up from leaf to root

B O(n) because all elements might need to be checked

C O(1) because only one swap is needed

D O(n log n) because bubble up is repeated for each element

💡 Hint

Consider the height of the heap and how many swaps bubble up can perform.

Bubble up moves the inserted element up the tree at most the height of the heap, which is log n for a heap of size n.

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