Heap Structure Property

  • Describe the structure property of binary heap.

A complete binary tree is one where the tree is "full" on all levels except possibly the last, and the last level has all its nodes to the left side. (Contrast this with a perfect binary tree that you have learned about in an earlier chapter.)

Exercise Which of the following are a complete binary tree?

Solution

The two on the top are complete binary trees, but the bottom two are not. The bottom left one does not have all its nodes at the last level to the left side. In the bottom right one, level 2 is not full!