Heap data structure is created on the concept of complete binary tree. The height of the tree can be calculated as the height of the root. The height of the node in a tree is referred to the number of edges on the simple longest downward path from the node to the leaf.

The heap of size n with the height h has the following characteristics:

• The height of heap is log n.

• The total number of leaves in the heap are n/2.

• The number of nodes of the height h is less than equal to.

Use induction method to show that there are the at most nodes with height h in any kind of heap of n - element.

For the heap size of n which is greater than zero, the number of leaves is , assume that tree is nearly a complete binary tree.

Base case:

• The number of leaves at the height of h is equal to zero or the number of leaves in the heap of n element at height is zero.

• The parent of last node will be node at , it is the last parent for the heap. It means, after this node all nodes will be counted as leaves.

• Hence the count of number of leaves is equal to the , which shows that the base case is completely true.

Now suppose that at the height of number of nodes is given by formula.

If all the leaves are removed from the existing heap, nodes which are placed at the height 1 will be counted as the leaves in new heap and have the zero height.

In the same way all nodes for the new one tree will have one less than height from the old height. Use it in the induction step.

Induction:

• Consider that tree T_old of n-node, which have the N_h number of node at the height of h and T_new is the formed tree after removing the leaves from T_old tree. The tree T_new has the nodes as: .

• The number of nodes at the height of h in T_old would be same at the height of the in the T_new tree. Assume that represents the number of node at the height of in T_new tree.

Hence it is prove that there are the at most nodes with height h in any kind of heap of n -element.