Heap Shape vs Heap Order
What you'll learn: You'll understand the two independent requirements that make a binary heap valid—one about structure, one about values.
Two Separate Rules
A valid heap must satisfy two completely independent properties:
-
Heap Shape (Structural): The tree must be a complete binary tree. This means all levels are fully filled except possibly the last, which fills from left to right with no gaps. This property has nothing to do with the values stored—it's purely about the tree's geometry.
-
Heap Order (Value-based): The values must satisfy the min-heap or max-heap ordering property. In a max-heap, every parent is ≥ its children; in a min-heap, every parent is ≤ its children. This property has nothing to do with the tree's shape—it's purely about comparing node values.
Why They're Independent
Think of it like a bookshelf rule system:
- Shape rule: "Books must fill shelves left-to-right, top-to-bottom, no gaps."
- Order rule: "Parent books must be alphabetically before child books."
You could violate one without violating the other! A tree could be perfectly shaped (complete binary tree) but have values in the wrong order. Or it could have correct value ordering but have structural gaps that break completeness.
Checking Both Properties
When validating a heap, you must verify:
- Shape: Is every level filled left-to-right? (Usually guaranteed by array representation)
- Order: Does every parent-child pair satisfy the heap property?
Both must be true. A structure that's complete but has misordered values isn't a heap. Similarly, correctly ordered values in an incomplete tree aren't a heap either.
Key Takeaway: A binary heap requires both complete tree shape (structural property) and heap ordering (value property)—they are separate, independent requirements that must both hold.