Height of heap with n elements

Question

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.

Answer 1

As you know heap is a complete binary tree.

Let's look at some heap:

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