The height of a binary heap is the number of edges on the longest path from its root to a leaf. A binary heap with n nodes has height equal to the floor of log₂ n because its levels are filled from top to bottom and from left to right.
Heap Height Relation
The height of a binary heap is the number of edges on the longest path from its root to a leaf. A binary heap with n nodes has height equal to the floor of log₂ n because its levels are filled from top to bottom and from left to right.
\(h = \lfloor \log_{2} n\rfloor\)
What this formula means
Scientific principle
Principle
A binary heap is a complete binary tree. Each level can contain twice as many nodes as the previous level. Consequently, a heap with h edges from root to deepest leaf contains at least 2ʰ and at most 2ʰ⁺¹ − 1 nodes.
Derivation
1. The root is at level zero and contains one node.
2. Level one can contain at most 2 nodes.
3. Level two can contain at most 4 nodes.
4. A complete binary tree of height h has between 2ʰ and 2ʰ⁺¹ − 1 nodes.
5. Therefore, 2ʰ ≤ n < 2ʰ⁺¹.
6. Taking base-2 logarithms gives h ≤ log₂ n < h + 1.
7. Thus, h = ⌊log₂ n⌋ for n ≥ 1.
Final Result
h = ⌊log₂ n⌋
Minimum Nodes At Height
n_min = 2ʰ
Maximum Nodes At Height
n_max = 2ʰ⁺¹ − 1
Level Count
L = ⌊log₂ n⌋ + 1
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
h | Heap height measured in edges | Tree levels or edges |
n | Number of nodes in the heap | Nodes |
L | Number of occupied levels | Levels |
SI units and conversions
Height
Edges
Node Count
Nodes
Complexity Relation
Θ(log n)
Conditions of use
The structure is a binary heap represented as a complete binary tree.
The heap contains at least one node.
Height is measured as the number of edges from the root to a deepest leaf.
The relation applies to both min-heaps and max-heaps.
Limitations and assumptions
The formula does not describe the height of an arbitrary binary tree.
If height is measured in nodes rather than edges, the result is ⌊log₂ n⌋ + 1.
A heap's shape is complete, but its values do not need to be sorted.
The equation does not determine which values appear at particular levels.
A one-node heap has height zero under the edge-count convention.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
Calculate the height of a binary heap containing 100 nodes. |
| The heap height is 6 edges, corresponding to 7 occupied levels. |
A complete binary heap contains 31 nodes. Determine its height and maximum possible number of nodes at that height. |
| The heap height is 4 edges, and it can contain at most 31 nodes at that height. |
Real-world applications
Binary heap analysis
Priority queue implementation
Heap insertion and deletion analysis
Heap sort complexity analysis
Tree-based data structure design
Formula Meaning
The height of a binary heap is the number of edges on the longest path from its root to a leaf. A binary heap with n nodes has height equal to the floor of log₂ n because its levels are filled from top to bottom and from left to right.
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.