What is Heap?
Heap is a binary tree-based data structure but with two conditions.
- It should be a complete binary tree.
- All the nodes of the tree should follow a specific order.
The ordering can be of 2 types:
- Max-Heap: In this type of heap, the value of the parent node is greater than or equal to the value of its child nodes. The greatest value is at the root. The same property must be true for all subtrees.
- Min-Heap: In this type of heap, the value of the parent node is smaller than or equal to the value of its child nodes. The smallest value is at the root. The same property must be true for all subtrees.
Note: Heaps don’t need to be sorted in ascending or descending order.
Implementation of Heap:
Let’s try to understand the construction of a Max-Heap.
To insert a node in a Max-Heap, we will follow 4 simple steps:
- Create an empty node at the end of the heap.
- Insert the value in the newly created node.
- Look at the parent node. If the value of the parent node is less than this child node, simply swap them.
- Repeat the above step until Heap property holds.
Now, we are going to take an unsorted array and convert it into a Max-Heap. To do this we will implement a function (max_heapify here) that can maintain the property of max heap.
Deletion
- Removing the largest element
Because Max-Heap has the largest element at the root node, we know exactly where it is in our array.
If we want to delete the element, we must shift the entire tree upwards to fill the root node’s place. To do this, again we’ll follow 4 simple steps:
- Delete the root node.
- Take the last node of the last level directly to the top, replacing the deleted node.
- Compare the new root to its children. If it is smaller than either child, swap the node with the smaller of the two children.
- Repeat the above step until Heap property holds.
Here are the functions which are deleting the root node (delete_root) and maintaining the Max_Heap property (max_heapify).
Similarly, we can insert or delete nodes in Min-Heap as well but then we’ll go for the smallest values instead of the largest ones.
Time Complexity:
For Insertion:
Complexity of adding a node is: O(1)
Let’s consider a Complete Binary tree of height H and N nodes, so complexity of swapping the nodes(upheapify) is: O(H) = O(log N)
Total complexity : O(1) + O(logN) = O(logN)
For Deletion:
Complexity of swapping leaf node with parent node is: O(1)
Let’s consider a Complete Binary tree of of height H and N nodes, so complexity of swapping the nodes(downheapify)is : O(H) = O(log N)
Total complexity : O(1) + O(logN) = O(logN)
Priority Queue in C++
Since we have got our basics cleared and know how to build a heap, we can now easily use the built-in priority queue in C++.
Whenever elements are pushed or popped, the heap structure is maintained according to the priority queue declaration.
Check out this link to read about priority queue in detail.
heapq in Python
Similar to the priority queue, we have a heapq module in Python that we can use to build a min-heap quickly. Whenever elements are pushed or popped, the heap structure is maintained.
If you want to implement a max heap with heapq, enter your values as negative values and when you want to pop values from your max heap, change the sign of the popped value back to positive.
Check out the Python docs on heapq to expand your knowledge.
Thanks for reading and for any queries connect with me through LinkedIn!
