✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-COM-2069

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

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.

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

SymbolMeaningUnit

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

ProblemSolutionAnswer

Calculate the height of a binary heap containing 100 nodes.

  • Given: n = 100.

  • Use: h = ⌊log₂ n⌋.

  • log₂ 100 ≈ 6.644.

  • h = ⌊6.644⌋ = 6.

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.

  • Given: n = 31.

  • h = ⌊log₂ 31⌋ = 4.

  • Maximum nodes at height h = 2ʰ⁺¹ − 1.

  • n_max = 2⁵ − 1 = 31.

  • Therefore, all levels from zero through four are completely filled.

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.

← Back to Formula Hub · Suggest a correction or source