What are nearly complete binary trees?

Question

I have read many definitions of a "heap" online, and I have also read the definition in CLRS. Most of the definitions online seem to say that heaps are complete binary trees; however, CLRS starts the heap chapter with the following sentence:

The (binary) heap data structure is an array object that we can view as a nearly complete binary tree...

I'm not sure why, but it really bothers me that CLRS calls heaps "nearly complete," whereas almost every other definition of "heap" I've read calls heaps "complete."

This leads me to the following question: Is it possible to have a heap that isn't a complete binary tree?

Answer 1

What exactly complete means? People have different opinions. In context of heap, complete binary tree should mean last level of tree has maximum number of nodes.

Any heap not having maximum leaves in its last level is not complete or is nearly complete.

For example, a heap with 7 elements would be complete binary tree. But a heap with 4, 5 or 6 elements wouldn't have its last level completely filled i.e nearly complete.

A heap with Nearly complete binary tree of depth three (assuming depth of root node to be 1) looks like below:

Answer 2

You are absolutely right to be bothered by the expression "nearly complete". A heap is a complete binary tree, according to the most common terminology:

• complete binary tree: all except the last level are fully occupied, and the leaves in the last level appear at the left side of that level.

• perfect binary tree: a complete binary tree where also the last level is completely occupied.

• full binary tree: a binary tree where none of the nodes has just one child. Sometimes this term is used to denote a perfect binary tree, adding to the confusion.

A perfect binary tree is also a complete and a full binary tree, but a complete binary tree may or may not be a full binary tree.

But the Wikipedia article on Binary tree warns:

Some authors use the term complete to refer instead to a perfect binary tree [...] in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.

So apparently the author of the text you refer to, falls into that category.