"Let H be the height of the tree. If the heap is not a complete binary tree (because the bottom level is not full), then the nodes at a given depth don’t all have the same height. Eg., although all the nodes with depth H have height 0, the nodes with depth H-1 may have either height 0 or 1"
Found this explanation when searching for the explanation of statement --"max node with given height h in N-element heap = N/2^(h+1)" as per CLRS.
Does this means that different level (different depth) node can have same height?
I know that no. of leaves in a heap is N/2, does this somehow related???
For example, this is a valid heap:
__1__
/ \
3 5
/ \ / \
4 9 6 10
/ \
7 11
Now compare the situation of node 5 and node 4. They are at a different level (i.e. at a different depth), but have the same height (i.e., the subtrees that they root have the same height).
On the other hand, we have node 3 and 5 that are on the same level, but they have a different height.
A note about terminology. The quote has "If the heap is not a complete binary tree...". Other sources will define the above example as a "complete binary tree", while a tree that has all its leaves at the bottom level would be called a "perfect binary tree". So I would read that quote as "If the heap is not a perfect binary tree...". See Wikipedia:
Some authors use the term complete to refer instead to a perfect binary tree as defined above
This is obviously confusing and means we always need to verify what an author means with these terms.