Heap Extract Min or Max Bubble Down in DSA C++ - 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 element?

The 'bubble down' operation restores the heap property by moving the new 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 continue bubbling down in a max-heap.

In a max-heap, bubbling down continues as long as the current node is smaller than at least one of its children. The node swaps with the larger child to maintain the max-heap property.

intermediate

What is the time complexity of the extract min or max operation including 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 proportional to log n.

beginner

Why do we use the last element of the heap to replace the root during extraction?

Using the last element to replace the root keeps the heap complete (all levels fully filled except possibly the last), which is essential for the heap structure.

After extracting the root in a min-heap, what is the first step before bubbling down?

A Swap the root with its left child

B Replace the root with the last element

C Remove the last element

D Insert a new element at the root

The last element replaces the root to maintain the complete tree structure before bubbling down.

In a max-heap, bubbling down swaps the current node with which child?

A The larger child

B The right child only

C The left child only

D The smaller child

To maintain max-heap property, swap with the larger child if the current node is smaller.

What is the main goal of the bubble down operation?

A To delete the last element

B To insert a new element

C To restore heap property after extraction

D To sort the heap

Bubble down restores the heap property after the root is replaced during extraction.

What is the height of a heap with n elements?

A n

B n/2

C sqrt(n)

D log n

A heap is a complete binary tree, so its height is proportional to log n.

Which element is removed during the extract min or max operation?

A The root element

B The last element

C The leftmost leaf

D The rightmost leaf

The root element (min or max) is removed during extraction.

Explain step-by-step how the bubble down operation works after extracting the root from a min-heap.

Think about how to keep the smallest element at the root.

Describe why the heap remains a complete binary tree after extracting the min or max element and bubbling down.

Focus on the shape and order of the heap.