Heap Data Structure | Min and Max Heap
Heap is specialized data structured, basically based on 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 does Heap differ from normal Tree?
Heap have the 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 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
Min Heap Data Structure:
In min heap, for every pair of parent and descendant child node, parent node have 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:
In max heap, for every pair of parent and descendant child node, parent node have 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.
- 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.
- It is the complete binary tree.
– All the nodes get filled before adding any node at next level
– If there is any right child node to parent node, there should have left node as well.
- There is no ordering between nodes at the same level (Sibling nodes).
- 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.
Operation 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 next level by considering it as the root node.
Note: Above Heapify algorithm is to Heapify element for max heap. For min heap, root node value has to replace with the lowest value of left and right child.
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 the time depending upon a 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 O(nLogn).
Find Max element in 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. O(1).
This is the same case for finding the minimum value in min heap.
Delete Max element from Heap:
Select root node as it max value in max heap. Replace root node with the last node of the heap. Heapify the newly selected root node.
Selecting root node and replacing it with the last node, takes constant time. So the complexity of deleting maximum element from the heap is same as heapify operation i.e. O(nLogn).
Find the following table for Heap operation complexity for insert, find and delete operations.
Note: This complexity is according to the operation on Max Heap Data Structure.
Use and Application of Heap Data Structure:
- Max Heap is used to find 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 find 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 root node).
- Heap is used in heap sort algorithm. Which is one of the efficient algorithm for sorting as it has a complexity of O(nLogn) for sorting.
- Heap is also used as priority queue as the most important node is always at the root.