Heap Order Property: Max-Heap
What you'll learn: You'll understand the max-heap invariant—the rule that keeps every parent greater than or equal to its children throughout the entire tree.
The Core Idea
A max-heap is a complete binary tree where every parent node contains a value greater than or equal to the values of its children. This property must hold true at every single node in the tree, from root to leaves.
Think of it like a corporate hierarchy where every manager must have a higher salary than their direct reports. The CEO at the root has the highest salary in the company, and as you move down the tree, salaries can only stay the same or decrease—never increase.
How It Works
In a max-heap:
- The root always contains the maximum value in the entire structure
- For any node at position
i, its value is ≥ its left child's value and ≥ its right child's value - Sibling nodes (children of the same parent) have no ordering requirement relative to each other
- This property cascades down: grandparents are greater than grandchildren, and so on
Example tree:
50
/ \
30 40
/ \ /
10 20 15
Notice: 50 ≥ 30 and 50 ≥ 40; 30 ≥ 10 and 30 ≥ 20; 40 ≥ 15. Every parent dominates its children.
Why It Matters
The max-heap property guarantees instant access to the largest element—it's always at the root. This makes max-heaps perfect for priority queues where you need to repeatedly extract the maximum value efficiently.
Key Takeaway: In a max-heap, every parent node must have a value greater than or equal to both of its children, ensuring the maximum element always sits at the root.