Heap Extract Min or Max Bubble Down in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the purpose of the 'bubble down' operation in a heap after extracting the min or max?

The 'bubble down' operation restores the heap property by moving the root element down the tree until it is in the correct position, ensuring the heap remains a valid min-heap or max-heap.

beginner

In a min-heap, after extracting the minimum element, which element replaces the root before bubbling down?

The last element in the heap replaces the root before the bubble down process begins.

intermediate

Describe the condition to decide when to stop bubbling down in a max-heap.

Stop bubbling down when the current node is greater than or equal to both its children or when it has no children.

intermediate

What is the time complexity of the extract min or max operation with bubble down in a heap of size n?

The time complexity is O(log n) because the bubble down operation moves down the height of the heap, which is logarithmic in the number of elements.

advanced

Show the first step of bubble down after extracting min from this min-heap: [2, 5, 3, 8, 10]. The last element is moved to root.

After removing 2, move 10 to root: [10, 5, 3, 8]. Compare 10 with children 5 and 3. Swap 10 with 3 (smallest child). New heap: [3, 5, 10, 8].

What element replaces the root in a heap after extracting the min or max?

A The largest child

B The smallest child

C A new random element

D The last element in the heap

After extraction, the last element moves to the root before bubbling down.

In a max-heap, when does the bubble down operation stop?

A When the current node is greater than or equal to its children

B When the current node is smaller than its children

C When the heap is empty

D After one swap

Bubble down stops when the node is larger or equal to its children, maintaining max-heap property.

What is the time complexity of the extract min or max operation in a heap?

A O(1)

B O(log n)

C O(n log n)

D O(n)

Extracting min or max requires bubbling down, which takes O(log n) time.

Which of these is NOT a step in the extract min or max operation?

A Bubble up the root element

B Remove the root element

C Replace root with last element

D Bubble down the root element

Bubble up is used when inserting, not when extracting.

In a min-heap, after bubbling down, the root element is:

A Random element

B The largest element

C The smallest element

D The last element

The root always holds the smallest element in a min-heap.

Explain the steps involved in extracting the minimum element from a min-heap and how bubble down restores the heap property.

Think about how the smallest element is removed and how the heap fixes itself.

Describe the difference between bubble down in a min-heap and a max-heap during extract operations.

Focus on which child is chosen to swap with in each heap type.