I could not figure out why complete binary tree is most suited for mplementing heap? why we cannot use full binary tree? WHy complete binary tree is the most suited for heap implementation?
A full binary tree is not necessarily well-balanced. For instance, this is a full binary tree:
1
/ \
2 3
/ \
4 5
/ \
6 7
/ \
8 9
/ \
10 11
In general, a full binary tree where any right child is also a leaf, has a height that is O(𝑛), more precisely, (𝑛−1)/2. This will be problematic for heaps, which rely on the tree being well balanced to keep its insert/delete operations within a time complexity of O(log𝑛).
Secondly, full binary trees always have an odd number of nodes (except when they are empty). This already makes them impractical, as obviously heaps should be able to have even sizes too.
However, binary heaps do not have to be complete binary trees. That is only required when their implementation is the well-known array-based one. But one could also implement a binary heap with an AVL tree, which is not necessarily a complete binary tree, but which still keeps the tree balanced and will have the same time complexities for the heap operations. But since the overhead of the pointer management is larger than working with indices in an array, the array representation leads to faster operations.
The choice for a complete binary tree comes into play when the implementation is array-based and not an explicit node-pointer representation. When you fill an array with values in level-order, and don't allow for gaps in the array (unused slots), then it follows that the tree is complete. Although you could imagine an array that allows for gaps, this would be an inferior choice, as it wastes space, with no gain to compensate for it.