In a min-heap held in an array, is that array sorted, and what does the heap property actually guarantee?
answer
- the invariant is local, not global
- which pairs does it actually constrain?
- siblings are never compared
- root-to-leaf paths are non-decreasing
- only index 0 is guaranteed
basics
~20 sA min-heap's array is not sorted. The property constrains only parent versus child, so every root-to-leaf path is non-decreasing while siblings may sit in any order. Only index 0 is guaranteed: it holds the minimum.
solid answer
~40 sThe heap property is a **local** invariant along parent-child edges only: in a min-heap every node is <= both of its children. Nothing relates two siblings, and nothing relates nodes on different branches. So the backing array is generally unsorted — the single guarantee it gives you is that the minimum sits at index 0. Take a matchmaking pool stored as `[12, 15, 40, 21, 18, 55, 43]` (0-indexed, children of `i` at `2i+1` and `2i+2`): it is a perfectly valid min-heap, yet the left child 21 is larger than its right sibling 18, and the rating 18 sits *after* the larger rating 40 in the array. That is exactly the trade: you buy an O(1) peek at the extreme and cheap maintenance, and you give up any global ordering.
go deeper
Be ready to state the invariant in one sentence — parent <= both children in a min-heap — and to say plainly that the array is not sorted. Practise verifying a small array by hand.
Explain why the invariant is deliberately weak: only edges are constrained, so repairs touch one root-to-leaf path and cost O(log n) instead of a full reordering.
Show the consequences in design terms: O(1) access to one extreme, O(n) to find anything else, and no ordered iteration — so know when a heap is the wrong choice for a workload.
Own the framing that a heap is the minimal structure satisfying an extreme-access requirement, and be able to say what a team gives up by choosing it over a structure that maintains a total order.
## The invariant, stated precisely A binary min-heap is a complete binary tree in which **every node's key is <= the keys of its children**. A max-heap flips the comparison: every node's key is >= its children's. That is the whole ordering rule. It says nothing about: - how a node compares to its **sibling**, - how a node compares to a **cousin** or any node on another branch, - how a node compares to anything **above its own parent chain**. Because the relation is transitive along edges, one consequence does follow: on any path from the root down to a leaf, keys are **non-decreasing** in a min-heap. The root is therefore <= every other key in the tree, which is why peek is O(1). That is the only global fact the invariant hands you. ## Why the array looks shuffled A heap of n elements is stored implicitly: the tree is read level by level, left to right, into array slots `0..n-1`. Consider a pool of player ratings for a matchmaking queue: ``` index: 0 1 2 3 4 5 6 value: 12 15 40 21 18 55 43 ``` Read as a tree: 12 is the root; its children are 15 (index 1) and 40 (index 2); 15's children are 21 and 18; 40's children are 55 and 43. Check every parent-child pair — 12<=15, 12<=40, 15<=21, 15<=18, 40<=55, 40<=43 — all hold, so this is a valid min-heap. Now look at the array as a sequence: 40 precedes 18, and 21 precedes 18. It is not sorted, not even nearly. Many different arrays represent heaps over the same multiset of ratings, and swapping two siblings produces another valid heap. ## The misconceptions this kills **"The array is sorted, or almost sorted."** It is not. Sorting is a *total* order over all n elements; the heap property is a *partial* order induced by the parent-child edges. A sorted array happens to satisfy the min-heap property (it is a valid heap), but the converse fails badly. **"The left child is smaller than the right child."** Nothing enforces this. If it did, a heap would carry strictly more information than it does, and maintaining it would cost more than the O(log n) the structure promises. **"Index 1 holds the second-smallest rating."** Close, but wrong as stated. The second-smallest element must be a **child of the root**, because every other node has an ancestor other than the root that is <= it. So it is at index 1 **or** index 2 — you must compare both. **"The maximum is at the last index."** The maximum of a min-heap must be a **leaf** (any internal node has a child that is >= it only in a max-heap; in a min-heap an internal node has a child that is >= it, so the maximum cannot have children strictly smaller — with distinct keys the maximum has no children at all). Leaves occupy roughly the second half of the array, indices `floor(n/2) .. n-1`, and the maximum can be any one of them. Finding it costs O(n) — really O(n/2) comparisons, still linear. ## What the weak guarantee buys you The invariant is deliberately weak, and that weakness is the feature. Restoring a *total* order after an insertion would cost O(n) work or force a much heavier structure; restoring the heap property costs only a walk along one root-to-leaf path, O(log n), because only the edges on that path can be violated. A heap is the minimal structure that keeps the extreme cheap. When you also need ordered iteration, range scans, or lookup by key, the heap gives you none of that and you need a different structure or a second index. ## Quick self-check Given any array, you can verify the min-heap property in O(n) by testing, for each index `i` from 0 to `floor(n/2)-1`, that `a[i] <= a[2i+1]` and (when `2i+2 < n`) `a[i] <= a[2i+2]`. Notice what the check never does: it never compares `a[2i+1]` with `a[2i+2]`, and it never compares two elements on different branches. That absence *is* the answer to this question.
- If the array is unsorted, why is reading the minimum still O(1)?Because the invariant is transitive along edges: the root is <= its children, which are <= their children, and so on to every leaf. So the root is <= every key in the structure, and the root always lives at index 0. No search is needed — you read one slot.
- Where can the largest rating be in a min-heap, and what does locating it cost?With distinct keys it must be a leaf, since any internal node is <= its children. Leaves occupy indices floor(n/2) through n-1, so it can be any of roughly n/2 slots and finding it costs O(n). If you need both extremes cheaply, you want a different structure such as a min-max heap or two coupled heaps.
- Is a sorted ascending array a valid min-heap?Yes. If a[i] <= a[j] for every i < j, then in particular a[i] <= a[2i+1] and a[i] <= a[2i+2], so the property holds everywhere. Sorting is strictly stronger than the heap property — which is why you can treat any sorted array as a heap for free, but never assume a heap is sorted.
It is a chain of command, not a seating chart: everyone outranks their direct reports, but two people in different departments have no defined order at all.
saying these in an interview costs you the question
- Says the backing array is sorted or nearly sorted
- Claims the left child is always smaller than the right
- Insists index 1 always holds the second-smallest element
- Believes the maximum of a min-heap sits at the last index
- Thinks the property orders whole subtrees, not just edges