Type of Heaps in DSA?
The two main Type of Heaps are : min-heap and max-heap. Both types are complete binary trees, meaning they are entirely filled on all levels except possibly for the last level, which is filled from the left to right.
1. min-heap
A min-heap is a binary tree where the value of each node is less than or equal to the values of it children. This Property ensures that the smallest value is always at the root of the tree. The key operations of a min-heap include insertion, deletion, and heapification, all of which maintain the min-heap property.
Properties of min-heap
- Root Node: – Contains the smallest elements.
- Subtree: – Each subtree of a node is also a min-heap.
- Completeness: – The tree is complete, meaning it is fully populated except possibly for the last level.
2. max-heap
A max-heap is a binary tree where the value of each node is greater than or equal to the values of its children. This Property ensures that the largest value is always at the root of the tree. Like min-heap, max-heaps also support insertion, deletion and heapification operations that maintain the max-heap property.
Properties of max-heap
- Root Node: – Contains the largest element.
- Subtrees: – Each Subtree of a node is also a max-leap.
- Completeness: – The tree is complete, ensuring efficient space utilization.