I am curious because I took a quiz and answered false to the question:
"The height of an AVL tree may be greater than the height of a binary heap with the same elements."
I have been trying to think of an example, but I just cannot figure it out. Does anyone know when this is the case?
Consider the following AVL-tree with 7-nodes. It has 4 levels. The form of a binary heap is determined by the number of its nodes. With seven nodes it would be the perfectly balanced binary tree with 3 levels.
An AVL-tree is height balanced, in the sense that the height of two sibling subtrees never differs by more than one. Leaves however may exist on several levels. Binary heaps are much more rigidly structured. Leaves exist only on two levels, and nodes are added level by level, from left to right.
The example tree is of a special type: it has the minimal number of nodes to get a tree of this height.
OK for an exercise, but it is quite uncommon to compare AVL-trees and binary heaps. The value of the nodes are ordered in completely different ways. Also binary heaps are in fact implemented as arrays, not as pointer structures.
