Heaps (Priority Queue)
A specialized tree-based data structure that satisfies the heap property.
Heap Structure (Min-Heap)
Every parent is smaller than its children.
Array Representation:
See the Logic in Motion
Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.Intuition
In a normal queue, items are processed First-In-First-Out (FIFO). But what if some tasks are more important than others?
A Heap (or Priority Queue) is like a to-do list where you always pull the most important (Max-Heap) or smallest (Min-Heap) item first, regardless of when it was added.
Concept
Heap Property:
- Max-Heap: Every parent node is greater than or equal to its children. The root is the maximum.
- Min-Heap: Every parent node is smaller than or equal to its children. The root is the minimum.
- Complete Binary Tree: The tree is completely filled, except possibly for the last level, which is filled from left to right.
How it Works
Heaps are usually implemented using an Array.
- Root is at index
0. - Parent of
iisfloor((i-1)/2). - Left Child of
iis2*i + 1. - Right Child of
iis2*i + 2.
Step-by-Step Breakdown
1. Check Root. It's the extremum (min/max).
2. Navigate down using indices.
3. Verify Heap Property at each node.
When to Use
- Priority Schedulers (OS tasks).
- Dijkstra's Shortest Path algorithm.
- Finding Top-K elements (e.g., K largest numbers).
When NOT to Use
- Searching for an arbitrary element (O(N) time).
- When strict FIFO/LIFO ordering is needed (use Queue/Stack).
How to Identify
"Get Max/Min efficiently", "Kth largest element", "Schedule tasks by priority".
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.