CODEWITHSUNDEEP
data-structuresbinary-treeheap
Prova12
Prova12

Reputation: 653

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:

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.

Upvotes: 4

Views: 29741

Answers (2)

Reuben ombaso
Reuben ombaso

Reputation: 1

calculate the total number of elements

def height(self): 
  return math.floor(math.log(n,2))+1

Upvotes: 0

Photon
Photon

Reputation: 2777

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

Upvotes: 15

Related Questions