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

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the heap array after inserting 15?

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

DSA C#

int[] heap = {10, 20, 30, 40, 50};
// Insert 15 and bubble up
// What is the heap array now?

A [10, 15, 30, 40, 50, 20]

B [10, 20, 15, 40, 50, 30]

C [10, 20, 30, 40, 50, 15]

D [15, 10, 30, 40, 50, 20]

💡 Hint

Remember that bubble up swaps the inserted element with its parent while it is smaller.

Inserting 15 adds it at the end: [10, 20, 30, 40, 50, 15]. Bubble up compares 15 with its parent 20 and swaps them, resulting in [10, 15, 30, 40, 50, 20].

❓ Predict Output

intermediate

What is the heap array after inserting 5?

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

DSA C#

int[] heap = {10, 15, 30, 40, 50, 20};
// Insert 5 and bubble up
// What is the heap array now?

A [5, 10, 30, 40, 50, 20, 15]

B [5, 10, 15, 40, 50, 20, 30]

C [10, 15, 30, 40, 50, 20, 5]

D [10, 15, 5, 40, 50, 20, 30]

💡 Hint

Bubble up swaps repeatedly until the inserted value is not smaller than its parent.

Insert 5 at the end: [10, 15, 30, 40, 50, 20, 5]. Bubble up swaps 5 with 30, then with 15, resulting in [10, 5, 15, 40, 50, 20, 30], then swaps 5 with 10, final heap: [5, 10, 15, 40, 50, 20, 30].

🔧 Debug

advanced

Why does this bubble up code fail to maintain heap property?

Consider this bubble up code snippet for a min-heap insert operation. Why does it fail to maintain the heap property?

DSA C#

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;
    } else {
      break;
    }
    index = parent;
  }
}

A It always moves index to parent even if no swap happened, causing unnecessary swaps.

B It never updates index, causing an infinite loop.

C It swaps only if heap[index] > heap[parent], which is wrong for min-heap.

D It swaps correctly but does not stop when heap property is restored.

💡 Hint

Check when the loop should stop during bubble up.

The code swaps when needed but always moves index to parent, even if no swap occurred. It should stop when no swap is needed to avoid unnecessary moves.

🧠 Conceptual

advanced

How many swaps happen when inserting 1 into this min-heap?

Given the min-heap array [5, 10, 15, 40, 50, 20, 30], how many swaps occur during bubble up after inserting 1?

DSA C#

int[] heap = {5, 10, 15, 40, 50, 20, 30};
// Insert 1 and bubble up
// How many swaps happen?

A 4

B 2

C 3

D 1

💡 Hint

Count swaps as 1 moves up comparing with parents until heap property holds.

Insert 1 at index 7. Swaps: 1 with 30 (1), then with 15 (2), then with 5 (3). Stops at root. Total 3 swaps.

🚀 Application

expert

What is the heap array after inserting 25 into this max-heap?

Given a max-heap array [50, 40, 45, 20, 30, 35], what is the heap array after inserting 25 and performing bubble up?

DSA C#

int[] heap = {50, 40, 45, 20, 30, 35};
// Insert 25 and bubble up
// What is the heap array now?

A [50, 40, 45, 20, 30, 35, 25]

B [50, 40, 45, 25, 30, 35, 20]

C 50, 40, 45, 20, 30, 35, 25]

D ]52 ,53 ,03 ,02 ,54 ,04 ,05[

💡 Hint

In max-heap bubble up, swap only if inserted value is greater than parent.

Insert 25 at end: [50, 40, 45, 20, 30, 35, 25]. Bubble up compares 25 with parent 45; 25 < 45, no swap. Heap unchanged except new element at end.

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