Heap insertion (bubble up) in Data Structures Theory - Mini Project: Build & Apply

Heap insertion (bubble up)

📖 Scenario: Imagine you are managing a priority queue for tasks where the highest priority task should always be at the top. You will learn how to insert a new task into a max-heap and maintain the heap property by bubbling the new element up.

🎯 Goal: Build a simple max-heap insertion process that adds a new element to the heap and restores the heap order by bubbling the element up.

📋 What You'll Learn

Create a list called heap representing a max-heap with given values

Create a variable called new_value with the value to insert

Write a loop that bubbles the new_value up the heap to maintain max-heap property

Insert the new_value into the heap and complete the bubble up process

💡 Why This Matters

🌍 Real World

Heaps are used in priority queues, scheduling tasks, and algorithms like heapsort.

💼 Career

Understanding heap insertion is important for software engineers working with efficient data structures and algorithms.

1

Create the initial max-heap list

Create a list called heap with these exact values: [40, 30, 20, 15, 10, 5] representing a max-heap.

Data Structures Theory

# Create the max-heap list called heap
# Your code here

Hint

Use square brackets to create a list and assign it to heap.

2

Set the new value to insert

Create a variable called new_value and set it to 35, the value to insert into the heap.

Data Structures Theory

heap = [40, 30, 20, 15, 10, 5]
# Create new_value variable and set it to 35
# Your code here

Hint

Assign the number 35 to the variable new_value.

3

Bubble up the new value in the heap

Append new_value to the end of heap. Then use a while loop with variable index to bubble the new value up. Inside the loop, compare the new value with its parent and swap if the new value is greater. Use integer division // to find the parent index.

Data Structures Theory

heap = [40, 30, 20, 15, 10, 5]
new_value = 35
# Append new_value to heap and bubble it up
# Your code here

Hint

Remember to stop bubbling up when the new value is not greater than its parent or when it reaches the root.

4

Complete the heap insertion

Ensure the final heap list maintains the max-heap property after insertion and bubbling up. The heap should now include new_value in the correct position.

Data Structures Theory

heap = [40, 30, 20, 15, 10, 5]
new_value = 35
heap.append(new_value)
index = len(heap) - 1
while index > 0:
    parent_index = (index - 1) // 2
    if heap[index] > heap[parent_index]:
        heap[index], heap[parent_index] = heap[parent_index], heap[index]
        index = parent_index
    else:
        break
# Finalize the heap insertion
# Your code here

Hint

The heap list should be correctly updated with the new value in its proper place.

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