In this article, we are going to discuss some of the differences between the two different types of heap, namely, max heap and min heap. A detailed comparison will be performed between the two. In the next section, we will break max heap and min heap along with suitable illustrations.
Definition of Min Heap and Max Heap
Let us have a recap of what heap is before moving forward to see min heap and max heap, as defined by in the paragraph given below.
Heap is a tree-based data structure that satisfies the property of complete binary tree where the key at the root must be minimum or maximum. The storage of heap is done on contiguous memory locations unlike general trees.
While the storage is done contiguously, the parent and child nodes ( both left and right ) across the levels of tree can be accessed using the formula mentioned above.
Min Heap :- The smallest element is located at the root of the tree in the min heap such that it is easier to pick the smallest element when heap pop is performed.
Max Heap :- The greatest element is located at the root of the tree in the max heap such that it is easier to pick the largest element when heap pop is performed.
The illustration stating the both is represented below:
Difference between Max Heap and Min Heap
| Max Heap | Min Heap |
|---|---|
| 1. The data at the root node should be greater than each of the child nodes. | 1. The data at the root node should be smaller than each of the child nodes. |
| 2. The element having the highest value has the highest priority assigned to it. | 2. The element having the lowest value has the highest priority assigned to it. |
| 3. The first value to be extracted is the maximum value. | 3. The first value to be extracted is the minimum value. |
| 4. It is used for the purpose of implementing Priority Queue. | 4. It is used for the purpose of implementing Dijkstra Graph Algorithm and Minimum Spanning Trees. |
| 5. It is used to sort the array in ascending order using Heap Sort. | 5. It is used to sort the array in ascending order using Heap Sort. |
| 6. Operations performed in Max Heap include Extract Maximum, Get Maximum and Insertion. | 6. Operations performed in Min Heap include Extract Minimum, Get Minimum and Insertion. |
| 7. The root of the tree must have the maximum value. | 7. The root of the tree must have the minimum value. |
Complexity Analysis of Min Heap and Max Heap
To get maximum or minimum element in either of the heaps, constant time i.e. O(1) is taken as the element having highest priority is present at the top of the tree heap.
Inserting an element in both max heap and min heap takes logarithmic time i.e. O(log(N)), that can also be deduced as the height of the tree in the heap in the worst case.
Deleting an element in both max heap and min heap takes logarithmic time i.e. O(log(N)).
Conclusion
In this article, we studied what is min heap, what is max heap and the differences that both the data structures share among them with respect to the heap data structure.
We hope you liked this article on Min Heap and Max Heap and expect to see you again at PrepBytes with an informative piece of information.
Frequently Asked Questions – Max Heap and Min Heap
1. State one application of min heap and max heap.
Ans. Max Heap is used to implement priority queue while min heap is used to implement Dijkstra Graph Algorithm to find the shortest path in a given graph.
2. What is a complete binary tree?
Ans. It is a specialized form of tree where all the levels of the tree must be filled except the last level of the tree. The last level must start filling from the left portion of the tree.
3. What are the operations performed on max heap and min heap?
Ans. Operations such as Extract (maximum or minimum) , Get (maximum or minimum), Insertion and Deletion are performed.