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?
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 isnearly 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.enearly complete
.A heap with
Nearly complete
binary tree of depth three (assuming depth of root node to be 1) looks like below: