What is Heap?
A heap is a tree based data structure where the tree is a complete binary tree that maintains the property that either the children of a node are less than itself (max heap) or the children are greater than the node (min heap).
Properties of Heap:
Structural Property: This property states that it should be A Complete Binary Tree.
For example:
Max Heap
Ordering Property: The heap should follow either Max-heap or Min-heap Property.
- If it is Min-heap, the parent node should be less than the child node and
- In the case of a Max-heap, the parent node should be greater than the child node.
These rules should be followed at each level but the order of bottom child nodes can change we can understand it with an example(We are taking Max heap as an example):
Max Heap(Figure 1)
Max Heap(Figure 2)
Is the structure of a Heap unique?
From the above two examples, we can see that the heap follows the Max-heap property. And here we can also see that in the first example the child nodes at the bottom level are (5 and 4), (6 and 3) but in the second nodes the child node at the bottom level are (4 and 5), (3 and 6). The place is changed of nodes at the bottom of the heap but it satisfies the condition of Max-heap.
- The order of child or leaf nodes is not fixed, So there will be 4! = 24 valid arrangements possible.
- So which arrangement we get is dependent on the order of insertions and removals or insertion and removal algorithms. Or in the case of making a heap from an array(O(n) case), the order of the array when we start.
Conclusion:
From the above images, we can conclude while building a heap, the structure of the heap is not Unique.