Now, if we analyze the time taken in forming the heap from n array elements would be n times, and then, also heapifying a single node takes a time of o(logn) complexity making it a total of O(n*logn) time complexity.<\/li>\n<\/ul>\nNow, reading the above Quick Think section we will have to think of some optimized approach to solving this problem which would obviously require less time complexity than above.<\/p>\n
When you carefully notice that in the given input array the leaf nodes need not be heapified as they already follow the heap properties also we can see that the binary tree is formed in the level order, traversing the array from start to end to build the tree level by level, so how and on which element we will be performing the heapify operation?<\/p>\n
As mentioned in the above paragraph we will find the position of the last non-leaf node and perform the heapify operation of each non-leaf node in reverse level order.<\/p>\n
Now, let\u2019s discuss the algorithm for building a heap from an array<\/p>\n
Algorithm:<\/h3>\n\n- Step-1:<\/strong> Get the index of the first non-leaf node through the relation (n \/ 2) – 1 and perform level order traversal from the last leaf node and heapify each node <\/li>\n
- Step-2 (Heap Function):<\/strong> Now, we will assume the index (while the heapify function was called) we have has the largest data node.<\/li>\n
- Step-3:<\/strong> Now, similar to the above step get the index of the left and the right child node <\/li>\n
- Step-4:<\/strong> Now, compare that if the left child node is greater than the current largest node then, the largest node would be the current left child <\/li>\n
- Step-5:<\/strong> Again, compare that if the right child node is greater than the current largest node then, the largest node would be the current right child<\/li>\n
- Step-6:<\/strong> If the current largest node is not the present index node then, we will have to swap the nodes to make it a max heap, then go to step 7<\/li>\n
- Step-7:<\/strong> Now, in the previous step we have swapped the two nodes to convert it to the max heap, so, we will again have to re-arrange all the nodes by heapifying the nodes again<\/li>\n<\/ol>\n
Implementation Of The Above Algorithm:<\/h3>\n\t\t\t\t\t\t
![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1661854225655-Article.jpg\")
<\/p>\n