- \n
- It is a data structure which is a complete binary tree<\/li>\n\n\n\n
- All the levels are completely filled except the last level<\/li>\n\n\n\n
- Heap has some order of values to be maintained between parents and their children<\/li>\n\n\n\n
- There are 2 variations of heap possible\n
- \n
- MIN HEAP\n
- \n
- Here the value of parent is always less than the value of its children<\/li>\n\n\n\n
- Hence root will be the minimum in the entire heap<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- MAX HEAP\n
- \n
- Here the value of parent is always more than the value of its children<\/li>\n\n\n\n
- Hence root will be the maximum in the entire heap<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
What is Heap Sort<\/strong><\/h2>\n\n\n\n
- \n
- It is one of the efficient sorting algorithm based on heap data structure<\/li>\n\n\n\n
- Here the given array to be sorted is assumed to be a heap<\/li>\n\n\n\n
- So for ith index\n
- \n
- The left child will become the element present at the 2*i+1 index in the array<\/li>\n\n\n\n
- The right child will become the element present at the 2*i+2\u00a0 index in the array<\/li>\n\n\n\n
- Parent of the ith index will be element present at (i-1)\/2 index in the array<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
- \n
- There are 2 major operations which are responsible for maintaining the heap\n
- \n
- Heapify\n
- \n
- This operation sets the order of values between the parent and its child<\/li>\n\n\n\n
- If we are dealing with the max heap, it will find the index having max value among the node and its children<\/li>\n\n\n\n
- If the index holding max value is not the parent, it will wap the parent with the child having the max value<\/li>\n\n\n\n
- Algo<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
heapify(arr , i)\n\tleftChild = arr [2*0 + 1];\n\trightChild = arr [2*0 + 2];\n \tmaxIndex = max( arr[i], leftChild, rightChild)\n \tif(i != maxIndex)\n \t\tswap(arr[i], arr[maxIndex])<\/code><\/pre>\n\n\n\n- \n
- Build MAXHEAP or MINHEAP\n
- \n
- This is responsible for setting parent-child order in the entire heap<\/li>\n\n\n\n
- This is the first function which is called to build the heap<\/li>\n\n\n\n
- It starts from the last parent in the tree because that is the first instance where the order may get disturbed<\/li>\n\n\n\n
- So it iterates from i=n\/2-1 to 0 and call heapify on every parent<\/li>\n\n\n\n
- Algo<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
buildMaxHeap(arr)\n\tfor(int i = n \/ 2 - 1; i >= 0; i--)\n \t\t heapify(arr, i);\n<\/code><\/pre>\n\n\n\n- \n
- In Heapsort, we deal with Maxheap.<\/li>\n\n\n\n
- As we know root will have the max value possible in the heap, we will swap it with the last element in the heap and reduce the heap size by 1.<\/li>\n\n\n\n
- Heap size is the variable that maintains the total number of elements to be considered in the heap<\/li>\n\n\n\n
- Then we call downward heapify on the root. It starts from setting the relationship between the root n d its children. If either of the children was maximum then heapify is called on it.<\/li>\n<\/ul>\n\n\n\n
What is Heapify<\/strong><\/h2>\n\n\n\n
The process of reshaping a binary tree into a Heap data structure is known as heapify. A binary tree is a tree data structure that has two child nodes at max. If a node's children nodes are heapified, then only heapify process can be applied over that node. A heap should always be a complete binary tree, i.e., except the bottom level of the tree, all the levels are completely filled. The bottom level is filled from left to right. Bottom-up order should be used to perform heapification.<\/p>\n\n\n\n
Example of Max-Heapify:<\/strong><\/p>\n\n\n\n
Let's take an input array R=[11,22,25,5,14,17,2,18].
Step 1: To create a binary tree from the array:<\/p>\n\n\n![\"\"](\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2021\/03\/image-65.png\")
<\/figure>\n\n\n\nStep 2: Take a subtree at the lowest level and start checking if it follows the max-heap property or not:<\/p>\n\n\n
![\"\"](\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2021\/03\/image-66-1024x342.png\")
<\/figure>\n\n\n\nStep 3: Now, we can see that the subtree doesn't follow the max-heap property. The children node must contain a lesser value than its parent node. We swap the key values between the parent node and the children node to ensure that the tree follows the max-heap property.
Let's continue examining all the subtrees from the lowest level to the top level :<\/p>\n\n\n![\"\"](\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2021\/03\/image-67-1024x357.png\")
<\/figure>\n\n\n\nStep 4: We don't need to change anything here as this subtree follows the max-heap property. Now, we look at the branches on the right side:<\/p>\n\n\n
![\"\"](\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2021\/03\/image-68-1024x343.png\")
<\/figure>\n\n\n\nStep 5: Again the subtree follows the max-heap property so, let's continue this process:<\/p>\n\n\n
![\"\"](\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2021\/03\/image-69-1024x356.png\")
<\/figure>\n\n\n\nStep 6: Here again, we can see that the root node's key value is not the largest among all the nodes in the tree. Hence, we swapped the root node's key values with the key value of its right children node to match the max-heap property.
Now, after the swap, we need to check the right subtree from the root node to see whether it follows the max-heap property or not:<\/p>\n\n\n![\"\"](\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2021\/03\/image-70-1024x340.png\")
<\/figure>\n\n\n\nStep 7: Finally, we have to check the whole tree and see if it satisfies the max-heapify property, and then we'll get our final max-heap tree:<\/p>\n\n\n
![\"\"](\"https:\/\/www.mygreatlearning.com\/blog\/wp-content\/uploads\/2021\/03\/image-72-1024x338.png\")
<\/figure>\n\n\n\nHeapsort Pseudo-code<\/strong><\/h2>\n\n\n\n
- \n
- First, call build max heap to set the heap initially<\/li>\n\n\n\n
- Once the heap is created, take the root and wap it will the last element of the heap<\/li>\n\n\n\n
- Reduce the size of the heap<\/li>\n\n\n\n
- Call max heapify of index 0 i.e, the new root of the heap<\/li>\n<\/ul>\n\n\n\n
Heapsort Algorithm<\/strong><\/h2>\n\n\n\n
Heapsort(arr)\n\tbuildMaxHeap(arr)\n\tfor (int i = n - 1; i >= 0; i--) {\n \t swap(&arr[0], &arr[i]);\n\t heapsize--;\n\t maxHeapify(arr,0);\n \t}\n\n<\/code><\/pre>\n\n\n\nHeapsort Algorithm Dry Run<\/strong><\/h2>\n\n\n\n
input:<\/p>\n\n\n\n
0<\/td> 1<\/td> 2<\/td> 3<\/td> 4<\/td><\/tr> 23<\/td> 10<\/td> 16<\/td> 11<\/td> 20<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n The first step - call build max heap<\/p>\n\n\n\n
0<\/td> 1<\/td> 2<\/td> 3<\/td> 4<\/td><\/tr> 23<\/td> 20<\/td> 16<\/td> 11<\/td> 10<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n For i=4<\/p>\n\n\n\n
0<\/td> 1<\/td> 2<\/td> 3<\/td> 4<\/td><\/tr> 20<\/td> 11<\/td> 16<\/td> 10<\/td> 23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n After i=3<\/p>\n\n\n\n
0<\/td> 1<\/td> 2<\/td> 3<\/td> 4<\/td><\/tr> 16<\/td> 11<\/td> 10<\/td> 20<\/td> 23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n After i=2<\/p>\n\n\n\n
0<\/td> 1<\/td> 2<\/td> 3<\/td> 4<\/td><\/tr> 11<\/td> 10<\/td> 16<\/td> 20<\/td> 23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n After i=1<\/p>\n\n\n\n
0<\/td> 1<\/td> 2<\/td> 3<\/td> 4<\/td><\/tr> 10<\/td> 11<\/td> 16<\/td> 20<\/td> 23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n After i=0<\/p>\n\n\n\n
0<\/td> 1<\/td> 2<\/td> 3<\/td> 4<\/td><\/tr> 10<\/td> 11<\/td> 16<\/td> 20<\/td> 23<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n <\/p>\n\n\n\n
Heapsort Time Complexity<\/strong><\/h2>\n\n\n\n
- \n
- Build max heap takes O(n\/2) time<\/li>\n\n\n\n
- We are calling for heapify inside the for loop, which may take the height of the heap in the worst case for all comparison. Therefore time complexity will become O(nlogn)<\/li>\n\n\n\n
- Best Time Complexity: O(nlogn)<\/li>\n\n\n\n
- Average Time Complexity: O(nlogn)<\/li>\n\n\n\n
- Worst Time Complexity: O(nlogn)<\/li>\n<\/ul>\n\n\n\n
Heapsort Space Complexity<\/strong><\/h2>\n\n\n\n
- \n
- No auxiliary space is required in Heapsort implementation that is we are not using any arrays, linked list, stack, queue, etc to store our elements<\/li>\n\n\n\n
- Hence space complexity is: O(1)<\/li>\n<\/ul>\n\n\n\n
Applications of Heap Sort<\/strong> <\/h2>\n\n\n\n
- \n
- K sorted array<\/li>\n\n\n\n
- K largest or smallest elements in an array\u00a0<\/li>\n<\/ol>\n\n\n\n
As Quicksort and Merge sort are better in practice, the Heap sort algorithm has limited usage. <\/p>\n\n\n\n
Heapsort in C <\/strong><\/h2>\n\n\n\n
- Build MAXHEAP or MINHEAP\n
- Heapify\n
- There are 2 major operations which are responsible for maintaining the heap\n
- MIN HEAP\n