Heap Insert Operation Bubble Up in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the bubble up operation in a heap insert?

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

beginner

In a min-heap, when does the bubble up operation stop?

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

intermediate

What is the time complexity of the bubble up operation in a heap insert?

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

Show the parent index formula used during bubble up in a heap stored as an array.

Parent index = (child index - 1) / 2 (integer division). This formula helps find the parent node to compare during bubble up.

beginner

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

Because inserting at the end may violate the heap property, bubble up fixes this by swapping the new element with its parent until the heap property is restored.

What does the bubble up operation do in a heap insert?

A Swaps the root with the last element

B Moves the new element up to restore heap property

C Removes the root element

D Deletes the last element

Bubble up moves the newly inserted element up to maintain the heap property.

In a max-heap, bubble up continues while the child is ____ than the parent.

A less

B equal

C greater

D not comparable

In a max-heap, bubble up swaps while the child is greater than the parent.

What is the parent index of the element at index 5 in a heap array?

A 2

B 3

C 1

D 4

Parent index = (5 - 1) / 2 = 2.

What is the worst-case time complexity of bubble up in a heap of size n?

A O(1)

B O(n)

C O(n log n)

D O(log n)

Bubble up takes O(log n) time because it moves up the height of the heap.

Where is the new element inserted before bubble up in a heap stored as an array?

A At the end of the array

B At the root

C In the middle of the array

D At the beginning of the array

New elements are inserted at the end of the array before bubble up.

Explain the bubble up operation during heap insert and why it is necessary.

Think about how the heap property might break and how bubble up fixes it.

Describe how to find the parent index of a node in a heap stored as an array and how this helps in bubble up.

Remember the heap is a complete binary tree stored in an array.