Heap Operations
Understand how a Binary Heap maintains its structure during Insert and Extract-Max operations.
Heap Operations
Ready
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
Maintaining the heap property requires re-shuffling elements when the tree changes.
When we Insert, we add to the end and "bubble up" (swim) to find the correct spot. When we Extract Max, we replace the root with the last element and "bubble down" (sink) to fix the order.
Concept
Heapify Logic:
- Swim (Shift-Up): Swap node with parent if it violates heap property. Repeat until root or correct.
- Sink (Shift-Down): Swap node with largest child if it violates heap property. Repeat until leaf or correct.
How it Works
The visualizer lets you insert custom values and extract the max element.
- Insert 45: 45 is added as a leaf. It swaps with its parent (20) because 45 > 20. It repeats until it satisfies the Max-Heap property.
- Extract Max: Root is removed. Last leaf replaces root. New root sinks down swapping with larger children.
Step-by-Step Breakdown
1. Insert(val): `arr.push(val)`. `swim(last_index)`.
2. ExtractMax(): Swap `arr[0]` and `arr[last]`. `arr.pop()`. `sink(0)`.
3. Swim(k): While `k > 0` and `arr[parent] < arr[k]`: Swap. `k = parent`.
4. Sink(k): While `2k+1 < N`: Find larger child. If `arr[k] < child`: Swap. `k = child`.
When to Use
- Implementing a Priority Queue.
- Streaming algorithms (median of data stream).
- Graph algorithms (Prim's, Dijkstra's).
When NOT to Use
- When you need to search for an arbitrary value (requires O(N) scan).
- When standard Sorting is sufficient.
How to Identify
"Dynamic inserts and get max", "Process elements by importance".
Stop Guessing, Start Mastering.
Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.