Heap Order Property: Min-Heap
What you'll learn: You'll understand the fundamental rule that makes a min-heap a min-heap—every parent must be smaller than (or equal to) its children.
The Core Rule
A min-heap is a complete binary tree with one special invariant: every parent node contains a value that is less than or equal to the values of both its children. This property must hold throughout the entire tree, from root to leaves.
This means:
- The smallest element in the entire heap is always at the root
- As you move down any path from root to leaf, values never decrease (they stay the same or increase)
- Sibling nodes have no required ordering relationship—only parent-child pairs matter
An Everyday Analogy
Think of a corporate hierarchy where each manager must have less seniority time than anyone they supervise. The CEO has the least seniority, department heads have more, and individual contributors have the most. When you want to find the newest employee (minimum seniority), you always look at the top!
Example Structure
3
/ \
5 8
/ \
9 7
This is a valid min-heap because:
- 3 ≤ 5 and 3 ≤ 8 (root's children)
- 5 ≤ 9 and 5 ≤ 7 (left child's children)
This is invalid:
5
/ \
3 8 ← INVALID! Parent (5) > left child (3)
Why It Matters
The min-heap property enables efficient priority queue operations. You can always access the minimum element in O(1) time—it's guaranteed to be at the root. Combined with the complete binary tree property you just learned, this structure maintains balance while keeping the smallest element readily accessible.
Key Takeaway: In a min-heap, every parent node must have a value ≤ both its children, ensuring the minimum element always sits at the root.