A Heap is a special Tree-based data structure in which the tree is a complete binary tree. There are two types of heaps: Min-heap and Max-heap. A min-heap is used to access the minimum element in the heap whereas the Max-heap is used when accessing the maximum element in the heap.
In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
Also Read: Difference Between Stack And Heap
Max Heap vs Min Heap
| MAX HEAP | MIN HEAP |
| In a Max-Heap the key present at the root node must be greater than or equal to among the keys present at all of its children. | In a Min-Heap the key present at the root node must be less than or equal to among the keys present at all of its children. |
| A Max-Heap uses the descending priority. | A Min-Heap uses the ascending priority. |
| In a Max-Heap the maximum key element present at the root. | In a Min-Heap the minimum key element present at the root. |
| In a Max-Heap, the largest element is the first to be popped from the heap. | In a Min-Heap, the smallest element is the first to be popped from the heap. |
| In the construction of a Max-Heap, the largest element has priority. | In the construction of a Min-Heap, the smallest element has priority. |
Also Read: Difference Between Stack And Queue Data Structures
What you need to know about min heap
- In a Min-Heap the key present at the root node must be less than or equal to among the keys present at all of its children.
- A Min-Heap uses the ascending priority.
- In a Min-Heap the minimum key element present at the root.
- In a Min-Heap, the smallest element is the first to be popped from the heap.
- In the construction of a Min-Heap, the smallest element has priority.
What you need to know about max heap
- In a Max-Heap the key present at the root node must be greater than or equal to among the keys present at all of its children.
- A Max-Heap uses the descending priority.
- In a Max-Heap the maximum key element present at the root.
- In a Max-Heap, the largest element is the first to be popped from the heap.
- In the construction of a Max-Heap, the largest element has priority.
Conclusion
Heap data structure is a complete binary tree that satisfies the heap property, where any given node is:
- always greater than its child node/s and the key of the root node is the largest among all other nodes. This property is also called max heap.
- always smaller than the child node/s and the key of the root node is the smallest among all other nodes. This property is also called min heap.