Hong Life CalculatorsUnderstanding the binary heap index calculator — concept and principle
A binary heap is usually stored not as linked nodes but as a plain array, with the tree structure implied by the positions. This calculator takes a 0-based array index and returns its parent, its two children and its depth in the tree. It is handy when writing or debugging heapsort, priority queues and sift-up or sift-down code.
How it is calculated
- Parent: ⌊(i − 1) ÷ 2⌋; index 0 is the root and has no parent.
- Children: left = 2i + 1, right = 2i + 2.
- Depth: ⌊log₂(i + 1)⌋, with the root at depth 0.
A child index is valid only if it is smaller than the heap size; otherwise that child does not exist.
The principle
A heap is a complete binary tree: every level is full except possibly the last, which is filled from the left. Reading the nodes level by level, left to right, gives the array order. Level d holds 2ᵈ nodes and starts at index 2ᵈ − 1. The root's children take slots 1 and 2, and each later node's two children follow right after those of the node before it, so node i's children land at 2i + 1 and 2i + 2; reversing that gives the parent formula. No pointers are needed, which saves memory and keeps the data cache-friendly. With 1-based indexing, used in many textbooks, the formulas become parent ⌊i ÷ 2⌋ and children 2i and 2i + 1.
Worked example
- Input: i = 5.
- Parent: ⌊(5 − 1) ÷ 2⌋ = ⌊2⌋ = 2.
- Children: 2 × 5 + 1 = 11 and 2 × 5 + 2 = 12, shown as 11, 12.
- Depth: ⌊log₂ 6⌋ = ⌊2.585⌋ = 2.
Check: depth 2 holds indices 3 to 6, and index 5 is the left child of index 2, whose children are 5 and 6.
| Node index (0-based) | Parent |
|---|---|
| 1.25 | 0 |
| 2.5 | 0 |
| 3.75 | 1 |
| 5 | 2 |
| 6.25 | 2 |
| 7.5 | 3 |
| 10 | 4 |
How to read the result
The depth tells you how many swaps a sift-up from this node can take at most. A heap of n items has height ⌊log₂ n⌋, so insert and remove-top run in O(log n). In a heap of size 12, index 5 has only a left child (11), because index 12 would be out of range. The last non-leaf node is at ⌊n ÷ 2⌋ − 1, where bottom-up heap construction starts.
Common mistakes
- Mixing 0-based and 1-based formulas, which silently corrupts the heap.
- Forgetting to check that child indices are below the heap size.
- Computing the parent with (i − 1) / 2 in a language where integer division rounds toward zero; for i = 0 that gives 0, not "no parent", so test i > 0 first.
Frequently asked questions
Is a heap the same as a sorted array?
No. A heap only guarantees each parent is no larger (min-heap) or no smaller (max-heap) than its children; siblings are in no particular order.
How long does it take to build a heap from n items?
Bottom-up construction takes O(n), faster than inserting items one by one, which takes O(n log n).
Why use a heap for a priority queue?
It gives the minimum or maximum in O(1) and supports insert and removal in O(log n) with no extra memory.
Sources: J. W. J. Williams, "Algorithm 232: Heapsort", Communications of the ACM 7(6), 1964 · R. W. Floyd, "Algorithm 245: Treesort 3", Communications of the ACM 7(12), 1964 · T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, MIT Press (heapsort)