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

Heap Insert Operation 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 build a simple max-heap insert operation that keeps the highest priority task at the root by bubbling up the newly inserted element.

🎯 Goal: Build a max-heap insert operation in C that inserts a new element into the heap array and bubbles it up to maintain the max-heap property.

📋 What You'll Learn

Create an integer array called heap with the initial elements: 50, 30, 20, 15, 10

Create an integer variable called heap_size and set it to 5

Insert a new integer element 40 at the end of the heap array and increase heap_size by 1

Implement the bubble up logic to maintain the max-heap property after insertion

Print the heap array elements separated by spaces after the bubble up operation

💡 Why This Matters

🌍 Real World

Priority queues are used in task scheduling, network packet management, and event simulation where the highest priority item must be processed first.

💼 Career

Understanding heap insertions and bubble up operations is essential for roles involving algorithms, system design, and performance optimization.

1

Create the initial heap array

Create an integer array called heap with these exact elements: 50, 30, 20, 15, 10. Also create an integer variable called heap_size and set it to 5.

DSA C

int heap[10] = {50, 30, 20, 15, 10};
int heap_size = 5;
// Your code here

Hint

Use an integer array with size 10 and initialize it with the given values. Then create an integer variable heap_size and assign 5.

2

Insert the new element at the end

Insert the integer 40 at the end of the heap array at index heap_size. Then increase heap_size by 1.

DSA C

int heap[10] = {50, 30, 20, 15, 10};
int heap_size = 5;
heap[heap_size] = 40;
heap_size++;
// Your code here

Hint

Place 40 at index heap_size in the array and then increment heap_size.

3

Implement bubble up to maintain max-heap

Write a while loop to bubble up the newly inserted element at index heap_size - 1. Use an integer variable index initialized to heap_size - 1. While index > 0 and heap[index] is greater than its parent heap[(index - 1) / 2], swap them and update index to the parent's index.

DSA C

int heap[10] = {50, 30, 20, 15, 10};
int heap_size = 5;
heap[heap_size] = 40;
heap_size++;
int index = heap_size - 1;
// Your code here

Hint

Use a while loop to compare the current element with its parent and swap if needed. Update the index to the parent's index after swapping.

4

Print the heap after insertion and bubble up

Use a for loop with variable i from 0 to heap_size - 1 to print each element of heap separated by a space. Then print a newline.

DSA C

int heap[10] = {50, 30, 20, 15, 10};
int heap_size = 5;
heap[heap_size] = 40;
heap_size++;
int index = heap_size - 1;
while (index > 0 && heap[index] > heap[(index - 1) / 2]) {
    int temp = heap[index];
    heap[index] = heap[(index - 1) / 2];
    heap[(index - 1) / 2] = temp;
    index = (index - 1) / 2;
}
for (int i = 0; i < heap_size; i++) {
    // Your code here
}

Hint

Use a for loop to print each element followed by a space, then print a newline.

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 larger than its parent

B. To remove the smallest element from the heap

C. To sort all elements in ascending order

D. To swap the root with the last element

Solution

1. Step 1: Understand heap property

   A max-heap requires each parent to be greater than or equal to its children.

2. Step 2: Purpose of bubble up

   When inserting, bubble up moves the new element up if it is larger than its parent to restore heap property.

3. Final Answer:

   To restore the heap property by moving the new element up if it is larger than its parent -> Option A

4. Quick Check:

   Bubble up fixes heap by moving new element up [OK]

Hint: Bubble up moves new element up to fix heap order [OK]

Common Mistakes:

• Thinking bubble up sorts the entire heap
• Confusing bubble up with removing elements
• Assuming bubble up swaps root with last element

2. Which of the following C code snippets correctly performs the bubble up step after inserting a new element at index i in a max-heap array heap?

easy

A. if (heap[i] > heap[i + 1]) swap(heap[i], heap[i + 1]);

B. 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; }

C. for (int j = i; j > 0; j--) { if (heap[j] > heap[j - 1]) swap(heap[j], heap[j - 1]); }

D. 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; }

Solution

1. Step 1: Identify correct bubble up condition

   Bubble up swaps while current element is greater than its parent at index (i-1)/2.

2. Step 2: Check code correctness

   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; } correctly uses a while loop with condition and swaps elements, updating index i to parent.

3. Final Answer:

   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; } -> Option D

4. Quick Check:

   Bubble up uses parent index (i-1)/2 and swaps if child > parent [OK]

Hint: Use parent index (i-1)/2 and swap if child > parent [OK]

Common Mistakes:

• Using < instead of > in condition
• Using for loop instead of while
• Swapping with next element instead of parent

3. Given the max-heap array heap = [50, 30, 40, 10, 20], what will be the heap array after inserting 45 and performing bubble up?

medium

A. [50, 45, 40, 10, 20, 30]

B. [50, 30, 45, 10, 20, 40]

C. [45, 30, 50, 10, 20, 40]

D. [50, 30, 40, 10, 20, 45]

Solution

1. Step 1: Insert 45 at the end

   Insert 45 at index 5: heap = [50, 30, 40, 10, 20, 45]

2. Step 2: Bubble up 45

   Parent of index 5 is (5-1)/2=2 with value 40. Since 45 > 40, swap them. New heap: [50, 30, 45, 10, 20, 40]

3. Final Answer:

   [50, 30, 45, 10, 20, 40] -> Option B

4. Quick Check:

   Inserted 45 bubbled up swapping with 40 [OK]

Hint: Insert at end, swap up if bigger than parent [OK]

Common Mistakes:

• Not swapping after insertion
• Swapping with wrong parent index
• Placing 45 at wrong position

4. Consider the following bubble up code snippet for a max-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 error in this code?

medium

A. Parent index calculation is incorrect

B. The loop should start from i = 1 instead of i > 0

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

D. Swapping elements is not needed in bubble up

Solution

1. Step 1: Analyze comparison operator

   Bubble up in max-heap swaps when child is greater than parent, so condition should be heap[i] > heap[parent].

2. Step 2: Identify error

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

3. Final Answer:

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

4. Quick Check:

   Max-heap bubble up swaps if child > parent [OK]

Hint: Use > to compare child and parent in max-heap bubble up [OK]

Common Mistakes:

• Using < instead of > in condition
• Incorrect parent index formula
• Skipping swaps in bubble up

5. You have a max-heap represented as an array: [60, 40, 55, 20, 30, 50]. You insert 65 at the end and perform bubble up. What is the final heap array after bubble up completes?

hard

A. [65, 60, 55, 20, 30, 50, 40]

B. [65, 40, 60, 20, 30, 50, 55]

C. [60, 40, 65, 20, 30, 50, 55]

D. [60, 40, 55, 20, 30, 50, 65]

Solution

1. Step 1: Insert 65 at the end

   Heap becomes [60, 40, 55, 20, 30, 50, 65]. Index of 65 is 6.

2. Step 2: Bubble up 65

   Parent index = (6-1)/2 = 2, value 55. Since 65 > 55, swap: [60, 40, 65, 20, 30, 50, 55].

3. Step 3: Continue bubble up

   New index = 2. Parent index = (2-1)/2 = 0, value 60. Since 65 > 60, swap: [65, 40, 60, 20, 30, 50, 55].

4. Final Answer:

   [65, 60, 55, 20, 30, 50, 40] -> Option A

5. Quick Check:

   Inserted 65 bubbled up swapping with 55 then 60 [OK]

Hint: Bubble up swaps repeatedly until parent is larger [OK]

Common Mistakes:

• Stopping bubble up after one swap
• Swapping with wrong parent index
• Not updating index after swap