Exercise 6.3-3

Show that there are at most nodes of height h in any n-element heap.

Answer

First we know that  nodes are leaves because of exercise 6.1-7. So being f(h) a function that gives us the number of nodes with height h of a heap of length n
we need to proof by induction that:

for the base case we have:

this holds because all the leaves have height 0. Let x be the number of nodes in a heap so that

so the number of leaves is

finally for inductive step we have:

Note: basically the idea is to "remove" each layer of leaves until we reach the ones with de desire heigth.