Heap Extract Min or Max Bubble Down in DSA Typescript - 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 root element down the tree, swapping it with its smaller (min-heap) or larger (max-heap) child until the heap order is correct.

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 to restore the heap property.

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 ensures the heap property is maintained by moving the out-of-place element down to a position where it is correctly ordered relative to its children.

beginner

Show the TypeScript signature of a bubble down function for a min-heap.

function bubbleDown(heap: number[], index: number): void

What element is removed during the extract operation in a min-heap?

A The largest element

B The last element

C The root element (minimum)

D A random element

In a min-heap, the root element is the minimum and is removed during extraction.

After removing the root in a max-heap, which element temporarily replaces the root before bubbling down?

A A new element

B The smallest element

C The second largest element

D The last element in the heap

The last element replaces the root temporarily before bubble down restores the heap.

During bubble down in a min-heap, you swap the current node with:

A The smaller child

B The larger child

C The parent node

D No one, you only move up

In a min-heap, bubble down swaps with the smaller child to maintain heap order.

When does the bubble down process stop?

A After one swap

B When the node is smaller (min-heap) or larger (max-heap) than its children or has no children

C When the heap is empty

D When the node reaches the root

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

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

A O(log n)

B O(n)

C O(1)

D O(n log n)

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

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

Think about how the heap property is maintained by moving the root down.

Describe why bubble down is necessary after extracting the min or max element from a heap.

Consider what happens to the heap shape and order after extraction.