I've read in many books that Binary Heaps are ALMOST COMPLETE Binary Trees. In my knowledge, Almost Complete Binary Trees have the 2nd last level unfilled ALWAYS and from L-R. And, Complete Binary Trees may or may not have the last element always filled, but 2nd last level must be always filled like in almost complete binary Trees.
In context to that, I've also read Binary Heaps **Must **Be ALMOST COMPLETE Binary Trees. I had to ask why? Can heaps not be implemented on FULL Binary Trees, or complete Trees?
While learning Binary Heaps and HeapSort, I've always had seen Almost Complete Binary Trees. I wonder why? Why never in fully filled binary trees ?
The confusion comes from the difference between the grammatical meaning of "almost complete binary tree" and the technical meaning of the same concept.
Grammatically,
<almost complete X>means that something close to being completely X, but not quite X. However, in technicalities,<almost complete X>often means that the thing is not further from being X than "almost complete".Technically, an almost complete binary tree is a binary tree that, if you ignore the last level n, then the sub-tree above it if a complete binary tree, each level (except for the last) having all possible nodes.
But, at the last level, an almost complete binary tree may or may not be complete. Nodes are inserted into an almost complete binary tree from top-to-bottom and from left-to-right, being on top for new node is of higher priority than being at left.
A complete binary tree has
sum(2^0 + 2^1 + ... + 2^n) = 2^(n+1) - 1 nodes and a height of log(2, n).
Therefore, a complete binary tree is a particular possible state of an almost complete binary tree.
https://iq.opengenus.org/almost-complete-binary-tree/
So, in this case, the "almost" does not mean "not quite but close". It rather means "not further from being close", which has completeness as a particular possible case.