Why is a complete binary tree most suited for heap implementation? [closed]

Question

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?

Answer 1

First of all, it is not possible to create a heap structure without it being tightly packed. Every item in the array has a position in the binary tree, and this position comes from the array index.

Also, it has several advantages like the following:

• Some operations of the heap have a time complexity of O(lgn) where n is the height of the tree, keeping the height of the tree at a minimum allows us to keep the time required for these operations at a minimum.

• All the items of the complete binary tree are stored in a contiguous manner in an array so random access is possible by keeping the heap as a complete binary tree

• The completeness ensures that there is a well-defined and efficient way to determine the new root when an element is removed, not using a complete structure would mean losing this advantage (which is why you should use heap in the first place).