Do you think IIT Guwahati certified course can help you in your career?
Introduction
In this article, we will try to grab hold of the first problem which comes when we start studying heap, that is, what are the steps for building a heap. Further, we will find out the complexities of the implementation which we are using while building a heap. To create a heap from some array with ‘n’ number of elements, we are expected to insert every element in the heap one by one. So without wasting any time let's get started.
What is a Heap?
A special tree-based data structure in which a complete binary tree is present. In this data structure, the root node or parent node is compared with its child node or leaf node and is arranged in accordance with the comparison.
Heaps are of two types. These are:
Maximum Heap
Minimum Heap
Heaps can be a little tricky Data Structure. So, for more clarity, we will use examples to understand both types of the heap.
Heapify is a crucial operation in heap data structures, particularly in maintaining the heap property after insertion or deletion. The time complexity of the heapify operation depends on the height of the binary tree, which is typically logarithmic with respect to the number of elements in the heap.
The time complexity of heapify can be expressed as O(log n), where 'n' is the number of elements in the heap. This complexity arises because heapify traverses the height of the heap, adjusting elements as necessary to maintain the heap property.
Example of a Perfect Complete Binary Tree
A perfect complete binary tree is a special type of binary tree in which all levels are completely filled except possibly for the last level, which is filled from left to right. This structure ensures that the tree is balanced and has the maximum number of nodes for its height.
In a perfect complete binary tree, each level except the last level contains the maximum number of nodes possible. For example, a perfect complete binary tree of height 'h' will have 2^h - 1 nodes.
Time Complexity analysis of building a Heap
Building a heap involves constructing a heap data structure from an array of elements. The typical approach for building a heap is to iteratively apply the heapify operation on each non-leaf node in reverse level order.
The time complexity of building a heap can be analyzed as follows:
Heapify Operation: The heapify operation has a time complexity of O(log n), where 'n' is the number of elements in the heap.
Number of Nodes to Heapify: In a binary tree, there are n/2 non-leaf nodes, as the last level may contain at most half of the total nodes. Therefore, the heapify operation needs to be applied approximately n/2 times during the build process.
Combining these factors, the overall time complexity of building a heap is O(n log n).
Here's a pseudocode for building a heap:
BuildHeap(array)
n = length(array)
for i from n/2 downto 1 do
Heapify(array, i, n)
In the pseudocode, the BuildHeap function iterates over each non-leaf node in reverse level order and applies the Heapify operation to each node to ensure the heap property is maintained.
Max Heap
While building a heap, that is, a Max Heap, the value of the root node or parent node is the greatest among all the values present in that heap. Every element, when building a heap of this type, is inserted in a way so that the top node of the tree contains the greatest value. For a better understanding, refer to the example below.
Again, we will consider an array of seven elements. Using these elements, we will understand what exactly is the maximum heap.
Input:
arr[] = {14, 24, 12, 11, 25, 8, 35}
Resultant max heap:
Algorithm for Max Heap
Step-1:
The first element to arrive is 14. Simply, a node will be created with a value of 14. The time complexity for this step will be O(1).
Step-2:
Now, the second element, 24 arrives. It is inserted in such a way that it becomes the left child of the root node. After insertion, we observe that the properties of the maximum heap are violated. So, we will swap the values of those two nodes to satisfy the property of the heap. We will see that 24 becomes the value of the root node and 14 is the value of its left child node.
Step-3:
The third element that comes into the picture is 12. It will be inserted in such a way that it becomes the right child of the root node. We see that the properties of the maximum heap are not violated. So, no swapping will be done and we will continue further.
Step-4:
The next element to arrive is 11. It will be inserted in such a way that it becomes the left child of the node with the value 14. We see that the properties of the maximum heap are not violated. So, no changes will be done and we will proceed further.
Step-5:
The fifth element to arrive is 25. Initially, it will be inserted in such a way that it becomes the right child of the node with the value 14. After insertion, we observe that the properties of the maximum heap are disturbed. So, at first, it will be swapped with 14. Again, we see that the properties of the maximum heap are not fulfilled. Once again swapping will be done. This time it will be swapped with the value present at the root node.
After this step, the value of the root node will be 25 which was previously 24.
Step-6:
The next element to arrive will be 8. It will be inserted in such a way that it becomes the left child of the node with the value 12. We see that the properties of the maximum heap are not disturbed. So, no changes will be done and we will proceed further.
Step-7:
Now, we are left with the last element which is 35. Initially, it will be inserted in such a way that it becomes the right child of the node with the value 12. After insertion, we observe that the properties of the maximum heap are violated. So, at first, it will be swapped with 12. Again, we see that the properties of the maximum heap are not fulfilled. Once again swapping will be done. This time it will be swapped with the value present at the root node.
After this step, the value of the root node will be 35 which was previously 25. In this way, the maximum heap is created.
Min Heap
While building a heap, that is, Min Heap, the value of the root node or parent node is the smallest among all the values present in that heap. Every element, when building a heap of this type, is inserted in a way so that the top node of the tree contains the smallest value. For a better understanding, refer to the example below.
Consider an array of seven elements. Using these elements, we will understand what exactly is the minimum heap.
Input:
arr[] = {15, 27, 14, 10, 30, 40, 5}
Resultant minimum heap:
Algorithm for Minimum Heap
The algorithm for the minimum heap is similar to that for the maximum heap.
Step-1:
The first element to arrive is 15. Simply, a node will be created with a value of 15. The time complexity for this step will be O(1).
Step-2:
Now, the second element, 27 arrives. It is inserted in such a way that it becomes the left child of the previously present node. After insertion, we observe that the properties of the minimum heap are not violated. So, no swapping will be done and we will continue further.
Step-3:
The third element that comes into the picture is 14. It will be inserted in such a way that it becomes the right child of the root node. We see that the properties of the minimum heap are violated. So, swapping will be done between the node containing value 14 and the root node. The value of the root node has now become 14.
Step-4:
The next element to arrive is 10. It will be inserted in such a way that it becomes the left child of the node with the value 27. We see that the properties of the minimum heap are violated. So, the value of this node will be swapped with the node containing value 27. Again, we see that the properties of the minimum heap are not fulfilled. Once again swapping will be done. This time it will be swapped with the value present at the root node.
After this step, the value of the root node will be 10 which was previously 14.
Step-5:
The fifth element to arrive is 30. Initially, it will be inserted in such a way that it becomes the right child of the node with the value 14. We see that the properties of the minimum heap are not violated. So, no changes will be done and we will proceed further.
Step-6:
The next element to arrive will be 40. It will be inserted in such a way that it becomes the left child of the node with the value 15. We see that the properties of the minimum heap are not violated. So, no changes will be done and we will proceed further.
Step-7:
Now, we are left with the last element which is 5. Initially, it will be inserted in such a way that it becomes the right child of the node with the value 15. After insertion, we observe that the properties of the minimum heap are disturbed. So, at first, it will be swapped with 15. Again, we see that the properties of the minimum heap are not fulfilled. Once again swapping will be done. This time it will be swapped with the value present at the root node.
After this step, the value of the root node will be 5 which was previously 10. In this way, the minimum heap is created.
Implementation Of Heap
The process of building a heap, whether it be a Maximum Heap or a Minimum Heap can be very fascinating if you are familiar with the concepts and how to implement them efficiently. Before going through the analysis part, it is better if you learn its implementation using any language. If you are facing any problems regarding this, you can refer to this blog of Implementation of Heap.
Analysis of Complexities of both the types of Heap
The first element inserted into the empty heap takes O(1) time which is the best case of Insertion.
In the non-empty heap, insertion is done with O(log n) time complexity for the worst cases. The swapping in such a case is also done with O(log n) time complexity.
If the number of elements to be inserted is ‘n’. The time complexity ‘log n’ which was for a single element is multiplied by n. Hence, the complexity for the maximum heap becomes O(n log n).
So, the average case of Insertion will be:
No extra space is required and therefore, we did not any extra memory. So, the space complexity here remains O(1).
Which property of the heap makes it work as a priority queue?
In heap, the value of the root node must be either more than or less than both of its children nodes depending on the type of the heap. This property of the heap makes it work as a priority queue.
List some applications of Heap Data Structure.
The applications of Heap Data Structure include:
Priority Queue
Graph Algorithms
Order Statistics
Embedded Systems
What is the runtime of Max Heapify?
The runtime of Max Heapify, which is a crucial operation in maintaining the max-heap property, depends on the height of the subtree rooted at the node where Max Heapify is applied.
What is the best case complexity of heapify?
The best-case complexity of heapify occurs when the element at the root of the subtree already satisfies the max-heap property, meaning it is larger than both of its children.
Conclusion
To summarize the talk, we looked at what is heap and its types. We also learned the complete steps of building a heap, that is, algorithms, done implementations, and analysis of those implementations for both types of the heap.
We hope the above discussion helped you understand the heap data structure in clearer terms and solve any problem that comes to you related to the heap.
85+ registered 