Heap Insert Operation Bubble Up in DSA Python - Build from Scratch

Heap Insert Operation Bubble Up

📖 Scenario: Imagine you are managing a priority queue for tasks where the smallest number means highest priority. You want to add a new task and keep the queue ordered so the highest priority task is always at the front.

🎯 Goal: You will build a simple min-heap insert operation that adds a new number to the heap and moves it up to keep the smallest number at the top.

📋 What You'll Learn

Create a list called heap with initial values representing a min-heap

Create a variable called new_value with the value to insert

Write code to insert new_value at the end of heap and bubble it up to maintain min-heap order

Print the final heap list after insertion and bubble up

💡 Why This Matters

🌍 Real World

Priority queues are used in task scheduling, network routing, and many algorithms where the smallest or largest element needs quick access.

💼 Career

Understanding heap operations is important for software engineers working on performance-critical applications, databases, and system design.

1

Create the initial min-heap list

Create a list called heap with these exact values: [10, 15, 20, 17, 25]

DSA Python

# Create the initial heap list
# Your code here

Hint

Use square brackets to create a list and include the numbers exactly as shown.

2

Set the new value to insert

Create a variable called new_value and set it to 8

DSA Python

heap = [10, 15, 20, 17, 25]
# Create the new_value variable
# Your code here

Hint

Use the assignment operator = to set new_value to 8.

3

Insert and bubble up the new value in the heap

Append new_value to heap and then use a while loop with variables index and parent_index to bubble up the new value until the min-heap property is restored

DSA Python

heap = [10, 15, 20, 17, 25]
new_value = 8
# Append new_value to heap and bubble it up
# Your code here

Hint

Remember to append the new value first. Then keep swapping it with its parent if it is smaller, updating the index each time.

4

Print the heap after insertion and bubble up

Print the heap list to show the final state after inserting new_value and bubbling it up

DSA Python

heap = [10, 15, 20, 17, 25]
new_value = 8
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
# Print the heap list
# Your code here

Hint

Use print(heap) to display the final heap list.

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 remove the smallest element from the heap

C. To sort all elements in the heap in ascending order

D. To add a new element at the bottom without any changes

Solution

1. Step 1: Understand heap property

   In a min-heap, every parent node is 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 if it is smaller than its parent to restore 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 new elements up to fix heap [OK]

Common Mistakes:

• Thinking bubble up sorts the entire heap
• Confusing bubble up with removing elements
• Assuming bubble up adds element without changes

2. Which of the following Python code snippets correctly performs the bubble up step after inserting a new element at the end of a min-heap list heap?

easy

A. while i > 0 and heap[i] < heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2

B. while i > 0 and heap[i] > heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2

C. for i in range(len(heap)): if heap[i] < heap[(i - 1) // 2]: swap(heap[i], heap[(i - 1) // 2])

D. if heap[i] < heap[i + 1]: swap(heap[i], heap[i + 1])

Solution

1. Step 1: Identify bubble up condition

   Bubble up swaps while current element is smaller than its parent.

2. Step 2: Check code correctness

   while i > 0 and heap[i] < heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2 uses a while loop with condition heap[i] < heap[parent], swapping and updating i correctly.

3. Final Answer:

   while i > 0 and heap[i] < heap[(i - 1) // 2]: heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]; i = (i - 1) // 2 -> Option A

4. Quick Check:

   Bubble up swaps smaller child with parent [OK]

Hint: Bubble up swaps while child < parent using index (i-1)//2 [OK]

Common Mistakes:

• Using > instead of < in condition
• Using for loop instead of while
• Swapping with wrong indices

3. Given the min-heap represented as a list heap = [2, 5, 8, 10, 15], what will be the heap list after inserting 1 and performing bubble up?

medium

A. [1, 2, 5, 10, 15, 8]

B. [1, 2, 8, 10, 15, 5]

C. [2, 5, 8, 10, 15, 1]

D. [1, 5, 2, 10, 15, 8]

Solution

1. Step 1: Insert 1 at the end

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

2. Step 2: Bubble up 1

   Compare 1 with parent at index 2 (value 8). Swap: [2, 5, 1, 10, 15, 8]. Then compare 1 with new parent at index 0 (value 2). Swap: [1, 5, 2, 10, 15, 8].

3. Final Answer:

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

4. Quick Check:

   Inserted 1 bubbled up to root [OK]

Hint: Insert at end, swap up while smaller than parent [OK]

Common Mistakes:

• Not swapping enough times
• Swapping with wrong parent index
• Leaving new element at the end

4. The following code attempts to insert a new element into a min-heap and bubble it up, but it has a bug. What is the error?

def insert(heap, val):
    heap.append(val)
    i = len(heap) - 1
    while i > 0 and heap[i] > heap[(i - 1) // 2]:
        heap[i], heap[(i - 1) // 2] = heap[(i - 1) // 2], heap[i]
        i = (i - 1) // 2

medium

A. The append method should be insert at index 0

B. The index update i = (i - 1) // 2 is incorrect

C. The comparison operator should be '<' instead of '>' to maintain min-heap property

D. The while loop condition should check i >= 0 instead of i > 0

Solution

1. Step 1: Analyze bubble up condition

   For min-heap, bubble up swaps when child is smaller than parent, so condition should be heap[i] < heap[parent].

2. Step 2: Identify error in code

   Code uses heap[i] > heap[parent], which is wrong and breaks min-heap property.

3. Final Answer:

   The comparison operator should be '<' instead of '>' to maintain min-heap property -> Option C

4. Quick Check:

   Bubble up swaps when child < parent [OK]

Hint: Use '<' to bubble up smaller elements in min-heap [OK]

Common Mistakes:

• Using '>' instead of '<' in condition
• Incorrect index updates
• Appending at wrong position

5. You have a max-heap represented as [90, 70, 80, 40, 50, 60]. You insert 85 at the end and perform bubble up. What will be the final heap list?

hard

A. [90, 85, 80, 70, 50, 60, 40]

B. [90, 70, 85, 40, 50, 60, 80]

C. [85, 70, 90, 40, 50, 60, 80]

D. [90, 70, 80, 40, 50, 60, 85]

Solution

1. Step 1: Insert 85 at the end

   Heap becomes [90, 70, 80, 40, 50, 60, 85].

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

   Compare 85 with parent at index 2 (80). Since 85 > 80, swap: [90, 70, 85, 40, 50, 60, 80]. Then compare 85 with new parent at index 0 (90). 85 < 90, stop bubbling up.

3. Final Answer:

   [90, 70, 85, 40, 50, 60, 80] -> Option B

4. Quick Check:

   Bubble up swaps larger child with parent in max-heap [OK]

Hint: In max-heap, bubble up swaps if child > parent [OK]

Common Mistakes:

• Not swapping enough times
• Confusing min-heap and max-heap conditions
• Leaving new element at the end