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

Recall & Review

beginner

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

The bubble up operation moves the newly inserted element up the heap to restore the heap property, ensuring the parent node is smaller (min-heap) or larger (max-heap) than its children.

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 when it reaches the root of the heap.

intermediate

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

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

Which index calculation is used to find the parent of a node at index i in a heap array?

The parent index is calculated as Math.floor((i - 1) / 2).

beginner

Explain the bubble up process with an example of inserting 5 into a min-heap [2, 4, 7].

Insert 5 at the end: [2, 4, 7, 5]. Compare 5 with parent 4. Since 5 > 4, no swap needed. Bubble up stops. Final heap: [2, 4, 7, 5].

What does the bubble up operation do after inserting a new element in a min-heap?

A Removes the smallest element

B Moves the element up until it is larger than its parent

C Moves the element down to maintain heap property

D Moves the element up until it is no longer smaller than its parent

In a min-heap, bubble up moves the new element up until it is no longer smaller than its parent.

What is the parent index of the node at index 6 in a heap array?

A 1

B 3

C 2

D 4

Parent index = Math.floor((6 - 1) / 2) = Math.floor(5 / 2) = 2.

When inserting into a max-heap, bubble up continues as long as the inserted element is:

A Larger than its parent

B Smaller than its parent

C Equal to its parent

D At the root

In a max-heap, bubble up moves the element up while it is larger than its parent.

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

A O(log n)

B O(n)

C O(1)

D O(n log n)

Bubble up moves up the height of the heap, which is log n.

If the newly inserted element is at the root after bubble up, what does it mean?

A Heap property is violated

B The element is the smallest or largest

C The heap is empty

D Heap property is restored

If bubble up reaches root, the element is the smallest (min-heap) or largest (max-heap).

Describe the bubble up operation during heap insertion and why it is necessary.

Think about how the heap keeps order after adding a new value.

Explain how to find the parent index of a node in a heap stored as an array and how it is used in bubble up.

Remember the formula involves dividing the current index.