Problems/702. Max Heap Mechanics
PrevNext

702. Max Heap Mechanics

MediumHeapPriority QueueSift UpSift Down

A Max Heap is a specialized complete binary tree structure designed for efficient priority operations. In a max heap, every parent node maintains a value greater than or equal to its children's values, meaning the largest item is always at the root.

This mechanic visualizes the two primary mutations:

  1. Insertion (Sift-Up): Placing a new value at the very end of the tree and bubbling it upwards until it respects the parent-child ordering.
  2. Extraction (Sift-Down): Removing the root maximum, replacing it with the last element in the tree, and sinking that element down by repeatedly swapping it with its largest child to restore the heap property.
Example 1
Input: heap = [25, 20, 10, 15, 8, 3], insert = 30
Output: heap = [30, 25, 10, 15, 8, 3, 20]
The value 30 is appended at index 6, then sifted up by swapping with its parent 10, and then parent 25, becoming the new root.
Example 2
Input: heap = [30, 25, 10, 15, 8, 3, 20], extractMax()
Output: heap = [25, 20, 10, 15, 8, 3], max = 30
The root 30 is swapped with the last element 20, then popped. 20 is sifted down by swapping with its larger child 25, restoring the heap.
Example 3
Input: array = [10, 8, 25, 15, 30, 20], heapify()
Output: heap = [30, 20, 25, 15, 8, 10]
Running sift-down starting from the last parent index down to index 0 reorganizes the unsorted array into a valid max-heap structure.
Visualizer
⌥

Visualizer will appear here