All patterns
Heaps
Trees
Intermediate
Interactive
Restore heap order by bubbling an inserted value upward.
Time
O(log n) insert
Space
O(1) auxiliary
ActiveComparingMatch / bestIn windowFrontierVisitedExcludedAnswer
No frames to display.
The idea
A max heap stores a complete tree in an array and keeps every parent at least as large as its children. Insertion appends a value, then swaps it upward until that invariant is restored.
Analogy
A reusable way to think about organizing and navigating structured data efficiently.
When to reach for it
- The relationships between values drive the algorithm.
- You need efficient traversal, lookup, or updates.
- An interview problem names or implies this structure.
Language-independent template
heap.append(value)
i = last index
while i > 0 and heap[parent(i)] < heap[i]:
swap parent and child
i = parent(i)Complexity — time O(log n) insert, space O(1) auxiliary.
Common mistakes
- Losing a pointer before saving its next target.
- Breaking the structure invariant during an update.
- Forgetting empty and single-node cases.
Practice progression
Canonical interview problems, ordered from foundation to advanced application.
Easy
Last Stone WeightLC 1046
Repeatedly remove and combine the two heaviest stones.
Medium
Find the kth largest value without fully sorting the array.
Hard
Merge k Sorted ListsLC 23
Merge k sorted streams efficiently.
Variations
Traversal
Insertion and deletion
Search and reconstruction