Search code examples
data-structuresbinary-treeheap

Height of heap with n elements

I am having the following question:

"The height of a tree is the length of the longest branch of the tree. From the definition of height, what is the height of a heap with n elements? Give a clear and precise explanation with your answer."

Heap = binary tree

I know that the number of a complete binary tree is 2^(n° of levels - 1)

So far I tried the following:

If there are three heaps (2 complete binary trees and 1 non complete binary tree) such that:

  • Heap A = is a complete binary tree, of height H
  • Heap B = is a binary tree of height with more nodes than A but less than C (so has same height as C - I think?)
  • Heap C = is a binary tree of height H + 1

I can say that the height of B is between the height of A and C and the number of elements of B is between 2^(n° levels of A - 1) and 2^(n° levels of C - 1).

But I am not sure how to what is the height of a heap with n elements.

Solution

  • As you know heap is a complete binary tree.

    Let's look at some heap:

    enter image description here

    We can see that:

    • if heap has 1 node it's height will be 1

    • if heap has from 2 to 3 nodes it's height will be 2

    • if heap has from 4 to 7 nodes it's height will be 3

    • ...

    • if heap has from 2^i to 2^(i+1) - 1 nodes it's height will be i

    Notice that the height of the heap increases only when we fill some level with nodes and start a new one.

    This only happens on nodes: 1, 2, 4, 8, 16, 32, ...

    So a heap with n nodes will have height floor(log2(n)) + 1