Heap Extract Min or Max Bubble Down in DSA Javascript - 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 to its correct position after extraction, 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 starts.

intermediate

What condition determines when to stop the bubble down process in a heap?

Bubble down stops when the current node is smaller (min-heap) or larger (max-heap) than both its children or when it has no children.

intermediate

Why do we swap the current node with the smaller (min-heap) or larger (max-heap) child during bubble down?

Swapping with the smaller or larger child maintains the heap property by ensuring the parent node is always less than (min-heap) or greater than (max-heap) its children.

advanced

Show the bubble down steps after extracting the max from this max-heap: [50, 30, 40, 10, 20]

1. Remove max (50), replace root with last element (20): [20, 30, 40, 10] 2. Compare 20 with children 30 and 40; swap with 40 (largest child): [40, 30, 20, 10] 3. Now 20 has no children, so stop. Final heap: [40, 30, 20, 10]

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

A The second last element

B The first child of the root

C A new random element

D The last element in the heap

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

In a min-heap, bubble down swaps the current node with which child?

A The larger child

B The smaller child

C The left child always

D The right child always

Swapping with the smaller child maintains the min-heap property.

When does the bubble down process stop?

A When the node is in correct order with children or has no children

B When the node is smaller than its children in a max-heap

C When the node is larger than its children in a min-heap

D After a fixed number of swaps

Bubble down stops when the heap property is restored or no children exist.

What is the time complexity of bubble down in a heap of size n?

A O(n)

B O(1)

C O(log n)

D O(n log n)

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

Which of these is NOT true about bubble down?

A It always swaps with the left child

B It restores heap property after extraction

C It swaps with the child violating heap property

D It stops when heap property is satisfied

Bubble down swaps with the smaller or larger child depending on heap type, not always left child.

Explain the bubble down process after extracting the root from a min-heap.

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

Describe why bubble down is necessary after extracting the max from a max-heap.

Consider what happens to the heap structure after removal.