Difference Between Min Heap and Max Heap in Data Structure
In this article, you will learn detail about heap data structure. Detail includes- the difference between min heap and max heap, their usage, and different insertion and deletion operations.
Table of Contents:
- What is Heap in Data Structure?
- How is Heap different from Tree?
- Difference Between Min Heap and Max Heap
- Operations on Heap Data Structure
- Usage and Applications of Heap Data Structure
- Frequently asked interview questions on Heap
What is Heap in Data Structure?
Heap is a specialized data structured, basically based on the tree data structure that satisfies the heap property.
Suppose node A is a parent of node B, there is a special ordering of the value of node A with respect to the value of node B.
This heap property applies across the heap for every parent-child node pairs.
How Is Heap different from normal Tree?
Heap has a special property. That makes it differ from Tree. Suppose there is any parent node A and child node B, there need to be in the specific ordering of the values of A and B. The ordering of value can be increasing or decreasing order. According to the ordering of parent and child node value, there are two types of heap data structure:
This ordering is not necessary for a tree data structure.
The ordering of the values can be increasing or decreasing order. According to the ordering of parent and child node values, there are two types of heap data structure:
- Min Heap Data Structure
- Max Heap Data Structure
Difference Between Min Heap and Max Heap
Let’s see Min and Max heap one-by-one. In the end, you will understand the major difference between the two.
Min Heap Data Structure Example:
In min heap, for every pair of the parent and descendant child node, the parent node has always lower value than descended child node.
The value of the nodes increases as we traverse from root to leaf node.
The root node has the lowest value.
Max Heap Data Structure Example:
In the max heap, for every pair of the parent and descendant child node, the parent node has always greater value than descended child node.
The value of the nodes decreases as we traverse from root to leaf node.
The root node has the greatest value.
Operations on Heap Data Structure:
There are multiple operations that carried out on heap data structure such as heap creation, selection, insertion, and deletion of a node from the heap.
While inserting or deleting a node from the heap, there is a need to maintain the heap property, this is carried out by the basic operation called Heapify.
Add a given element that needs to Heapify, at the root node. If root node value is greater than its left and right child, terminate. Else replace root node value with the greatest value of left and right child. Continue Heapify for same element node at the next level by considering it as the root node.
Note: Above Heapify algorithm is to Heapify element for the max heap. For min heap, root node value has to replace with the lowest value of the left and right child.
Insert Element in the Heap:
Add element at the end of Heap (Tree) Apply reverse Heapify method from bottom to root node.
Insertion operation involves heapify operation and it takes time depending upon the height of the tree. For n elements, the height of the binary complete tree is
(nLogn). So complexity to insert the element in the heap is
Find Max element in the Heap:
In the case of max heap, maximum number value node will be the root node. So we can find it in constant time i.e.
This is the same case for finding the minimum value in min heap.
Delete Max element from the Heap:
Select the root node as it max value in a max heap. Replace the root node with the last node of the heap. Heapify the newly selected root node.
Selecting the root node and replacing it with the last node, takes constant time. So the complexity of deleting a maximum element from the heap is same as heapify operation i.e.
Find the following table for Heap operation complexity for insert, find and delete operations.
Note: This complexity is according to the operation on the Max Heap Data Structure.
Usage and Applications of Heap Data Structure
- Max Heap is used to finding the greatest element from the array. If the array is already ordered as Max Heap, it takes constant time
O(1)to find the greatest number from the array. (Max heap have the greatest value at root node)
- Min Heap is used to finding the lowest elements from the array. If the array is already ordered as Min-Heap, it takes constant time
O(1)to find the lowest number from the array. (Min heap have the lowest value at the root node).
- Heap is used in heap sort algorithm. Which is one of the efficient algorithm for sorting as it has a complexity of
- Heap is also used as a priority queue as the most important node is always at the root.
Frequently asked questions about Heap in Interview:
Is Heap sorted?
Heap is partially sorted as it maintains ordering between parent and child node. It is not completely sorted as there is no specific ordering between sibling nodes.
What is the difference between min heap and max heap?
Hope you find the answer in this article for this question.
How to implements min and max heap in programming like C/Java?
Just like tree implementation, you can implement heap using Linked List data structure.
Each node in the Linked List will be having two links pointing to the two children nodes.
Is heap complete binary tree?
Yes, it is the complete binary tree.
- All the nodes get filled before adding any node at the next level.
- If there is any right child node to the parent node, there should have a left node as well.
What is the order of the sibling elements (elements at the same level) in heap?
There is no ordering between nodes at the same level (Sibling nodes).
Is heap similar to the stack or queue?
Many gets confuse and correlate heap with stack or queue.
Remember stack and queue are abstract data type while heap is the actual data structure.
If you have any further point to discuss on min heap and max heap, feel free to ask your doubt by commenting below.
Insertion and deletion of an element takes log(n) and not nlog(n) as mentioned above. The problem space gets divided in half in every iteration of heapify.