Heap insertion (bubble up) in Data Structures Theory - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the bubble up process in heap insertion?

The bubble up process restores the heap property by moving the newly inserted element up the tree until it is in the correct position.

beginner

In a max-heap, when does the bubble up process stop during insertion?

It stops when the inserted element is less than or equal to its parent or it becomes the root of the heap.

intermediate

What is the time complexity of heap insertion using bubble up?

The time complexity is O(log n), where n is the number of elements in the heap, because the element moves up at most the height of the heap.

beginner

Describe the relationship between parent and child nodes in a binary heap during bubble up.

During bubble up, the child node is compared with its parent. If the heap property is violated (child > parent in max-heap), they swap places to maintain the heap structure.

beginner

Why is bubble up necessary after inserting a new element at the end of the heap?

Because inserting at the end may break the heap property, bubble up fixes this by moving the new element up until the heap property is restored.

What is the first step after inserting a new element in a heap?

A Swap the root with the last element

B Remove the root element

C Place the element at the end and start bubble up

D Sort the entire heap

In heap insertion, the new element is added at the end, then bubble up is used to restore the heap property.

In a min-heap, bubble up continues as long as the child is:

A Less than the parent

B Greater than the parent

C Equal to the parent

D At the root

In a min-heap, bubble up moves the child up while it is less than its parent to maintain the heap property.

What is the maximum number of swaps during bubble up in a heap of size n?

A log n

B n

C n squared

D 1

The height of a binary heap is log n, so bubble up can swap at most log n times.

If the newly inserted element is larger than its parent in a max-heap, what happens?

A The heap is rebuilt

B They swap places

C Insertion stops

D The element is removed

In a max-heap, if the child is larger than the parent, they swap to maintain the heap property.

Where is the new element initially placed in the heap before bubble up?

A At a random position

B At the root

C In the middle

D At the end (last position)

New elements are inserted at the end of the heap array before bubble up adjusts their position.

Explain the bubble up process during heap insertion and why it is important.

Think about how the heap property is maintained after adding a new element.

Describe the difference in bubble up behavior between a max-heap and a min-heap.

Focus on the comparison direction for swapping.

Practice

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