Skip to interview prep
Apexed

193. Why is the height of a binary heap with n elements floor(log2 n)?

EasyPriority queues & heaps

Technical
Show model answer

From the node bounds, 2^h ≤ n < 2^(h+1). Taking log base 2 gives h ≤ log2 n < h + 1, so h is exactly floor(log2 n).

This is why insert (sift up) and extract (sift down) are O(log n): each touches at most one node per level. It also follows from the array layout: node i (1-based) sits at depth floor(log2 i), and the last node is index n.

Why is the height of a binary heap with n elements floor(log2 n) — Data structures & algorithms interview question — Apexed