Bird
Raised Fist0
Data Structures Theoryknowledge~20 mins

Heap insertion (bubble up) in Data Structures Theory - Practice Problems & Coding Challenges

Choose your learning style10 modes available
LearnWhyDeepVisualPracticeChallengeProjectRecallTime

Start learning this pattern below

Jump into concepts and practice - no test required

or
Recommended
Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong
Challenge - 5 Problems
🎖️
Heap Mastery Badge
Get all challenges correct to earn this badge!
Test your skills under time pressure!
🧠 Conceptual
intermediate
2:00remaining
Understanding the bubble up process in a min-heap

When inserting a new element into a min-heap, the bubble up process is used to restore the heap property. Which of the following best describes what happens during bubble up?

AThe new element is swapped with its parent repeatedly until it is no longer smaller than its parent or it becomes the root.
BThe new element is swapped with its children repeatedly until it is larger than both children or it becomes a leaf.
CThe new element is inserted at the root and then pushed down to the correct position by swapping with the larger child.
DThe new element is inserted at the end and no swaps are needed because the heap property is always maintained.
Attempts:
2 left
💡 Hint

Think about how the heap property is restored from the bottom up after insertion.

🚀 Application
intermediate
2:00remaining
Resulting heap after inserting an element

Given the min-heap represented as an array: [3, 5, 8, 10, 15], what is the array after inserting the element 4 and performing bubble up?

A[3, 5, 4, 10, 15, 8]
B[3, 4, 8, 10, 15, 5]
C[3, 5, 8, 10, 15, 4]
D]5 ,51 ,01 ,8 ,4 ,3[
Attempts:
2 left
💡 Hint

Insert 4 at the end, then swap with parent if smaller.

🔍 Analysis
advanced
2:00remaining
Time complexity of bubble up in a heap

What is the worst-case time complexity of the bubble up operation when inserting an element into a heap of size n?

AO(1) because only one swap is needed
BO(log n) because the element may move up the height of the heap
CO(n) because the element may need to be compared with all other elements
DO(n log n) because each swap takes log n time
Attempts:
2 left
💡 Hint

Consider the height of a heap and how many swaps might be needed.

❓ Comparison
advanced
2:00remaining
Difference between bubble up in min-heap and max-heap

How does the bubble up process differ when inserting into a min-heap versus a max-heap?

AIn a min-heap, bubble up swaps if the child is larger than the parent; in a max-heap, swaps occur if the child is smaller than the parent.
BBubble up is the same for both heaps; it always swaps if the child is equal to the parent.
CIn a min-heap, bubble up swaps if the child is smaller than the parent; in a max-heap, swaps occur if the child is larger than the parent.
DBubble up does not occur in max-heaps, only in min-heaps.
Attempts:
2 left
💡 Hint

Think about the heap property each type maintains.

❓ Reasoning
expert
3:00remaining
Effect of bubble up on heap structure after multiple insertions

Consider inserting the elements [20, 15, 30, 5, 10] one by one into an empty min-heap using bubble up after each insertion. What is the final heap array representation?

A[5, 10, 20, 15, 30]
B[5, 20, 10, 15, 30]
C[5, 15, 10, 20, 30]
D[5, 10, 30, 20, 15]
Attempts:
2 left
💡 Hint

Insert each element and perform bubble up step-by-step.

Practice

(1/5)
1. What is the first step when inserting a new element into a binary heap using the bubble up method?
easy
A. Add the new element at the end of the heap
B. Compare the new element with the root
C. Remove the smallest element
D. Sort all elements in the heap

Solution

  1. Step 1: Add new element at the end

    The new element is always added at the end of the heap to maintain the complete tree property.

  2. Step 2: Prepare for bubble up

    After adding, the element will be compared with its parent to restore heap order.

  3. Final Answer:

    Add the new element at the end of the heap -> Option A

  4. Quick Check:

    Insertion starts by adding at the end [OK]
Hint: New elements always start at the end before bubbling up [OK]
Common Mistakes:
  • Starting at the root instead of the end
  • Removing elements before insertion
  • Sorting the entire heap immediately
2. Which of the following correctly describes the condition to continue bubbling up in a min-heap after insertion?
easy
A. Never bubble up after insertion
B. Continue bubbling up if the new element is greater than its parent
C. Continue bubbling up if the new element is equal to its parent
D. Continue bubbling up if the new element is less than its parent

Solution

  1. Step 1: Understand min-heap property

    In a min-heap, parents must be less than or equal to their children.

  2. Step 2: Bubble up condition

    If the new element is less than its parent, it violates the heap property and must bubble up.

  3. Final Answer:

    Continue bubbling up if the new element is less than its parent -> Option D

  4. Quick Check:

    Bubble up when child < parent in min-heap [OK]
Hint: Bubble up when new element is smaller than parent in min-heap [OK]
Common Mistakes:
  • Bubbling up when new element is greater
  • Ignoring equality cases
  • Not bubbling up at all
3. Given a min-heap represented as an array: [2, 5, 8, 10, 15], what will be the array after inserting 1 and performing bubble up?
medium
A. [1, 2, 8, 10, 15, 5]
B. [1, 2, 5, 10, 15, 8]
C. [1, 5, 2, 10, 15, 8]
D. [2, 5, 8, 10, 15, 1]

Solution

  1. Step 1: Insert 1 at the end

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

  2. Step 2: Bubble up 1

    Compare 1 with parent 8 (index 2). Since 1 < 8, swap: [2, 5, 1, 10, 15, 8]. Then compare 1 with parent 5 (index 1). Since 1 < 5, swap: [2, 1, 8, 10, 15, 5]. Then compare 1 with parent 2 (index 0). Since 1 < 2, swap: [1, 2, 8, 10, 15, 5].

  3. Final Answer:

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

  4. Quick Check:

    Bubble up swaps until heap property restored [OK]
Hint: Insert at end, then swap up while smaller than parent [OK]
Common Mistakes:
  • Not swapping enough times
  • Swapping with wrong parent
  • Leaving new element at the end
4. Consider the following code snippet for inserting into a min-heap. What is the error? 
def bubble_up(heap, index):
    while index > 0:
        parent = (index - 1) // 2
        if heap[index] > heap[parent]:
            heap[index], heap[parent] = heap[parent], heap[index]
            index = parent
        else:
            break
medium
A. The comparison should be heap[index] < heap[parent] for min-heap
B. The parent index calculation is incorrect
C. The loop condition should be index >= 0
D. Swapping should happen only if heap[index] == heap[parent]

Solution

  1. Step 1: Analyze comparison logic

    For a min-heap, bubble up should swap when child is less than parent, not greater.

  2. Step 2: Identify correct condition

    The code uses '>' which is wrong; it should be '<' to maintain min-heap property.

  3. Final Answer:

    The comparison should be heap[index] < heap[parent] for min-heap -> Option A

  4. Quick Check:

    Bubble up swaps when child < parent in min-heap [OK]
Hint: Use < comparison for min-heap bubble up [OK]
Common Mistakes:
  • Using > instead of <
  • Wrong parent index formula
  • Incorrect loop condition
5. You have a max-heap represented as [20, 15, 18, 8, 10, 17]. You insert 19. After bubble up, what is the correct heap array?
hard
A. [20, 15, 18, 8, 10, 17, 19]
B. [20, 19, 18, 8, 10, 17, 15]
C. [20, 15, 19, 8, 10, 17, 18]
D. [20, 19, 18, 15, 10, 17, 8]

Solution

  1. Step 1: Insert 19 at the end

    Array becomes [20, 15, 18, 8, 10, 17, 19].

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

    Parent of index 6 is index 2 (value 18). Since 19 > 18, swap: [20, 15, 19, 8, 10, 17, 18]. Next parent is index 0 (value 20). Since 19 < 20, stop bubbling up.

  3. Step 3: Final heap array

    The final array is [20, 15, 19, 8, 10, 17, 18].

  4. Final Answer:

    [20, 15, 19, 8, 10, 17, 18] -> Option C

  5. Quick Check:

    Bubble up swaps child > parent in max-heap [OK]
Hint: In max-heap, bubble up while child is greater than parent [OK]
Common Mistakes:
  • Not swapping enough times
  • Swapping with wrong parent
  • Leaving new element at the end