🙏

জয়  শ্রী  রাম

🕉

---

Prerequisites:

1. Heap Implementation
2. Heapify

The algorithm for Heap Sort is really easy if you understand Fundamentals of Heap and Heapify really well.

For Heap Sort (ascending order) we use Max Heap. We know that in Max Heap the maximum value is the first element in the array that represents the heap. So we do a max heapify and then swap the first element (largest value) in the array with the last element (element at index (n - 1), since index is zero based) in the array. So now the largest value is in the correct place in the modified array, because the largest value should be at the end position of the array after sorting.

Now we do a max heapify on the first (n - 1) elements of the modified array and and swap the first element (which is the largest element among the first (n - 1) elements in the modified array) with the element at index (n - 2) in the zero-based indexed array. Once that is done we would repeat the process on the first (n - 2) elements in the modified array and so on till we reach index 0 of the array. n = total number of given elements. Notice that Heap Sort is in-place.

N.B: Since condition for calling Heapify on an array segment is that all the elements in the segment except the first element MUST already maintain heap property, we need to start with a Max Heap already. So, as we will see in the code, we would call BUILD_MAX_HEAP at first to build the max heap. Heapify is must read if you don't know what I am talking about.

Algorithm:

1. Build a max heap from the input data.
2. At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of the tree.
3. Repeat step 2 while size of heap is greater than 1.

Please take a look at the below simple code and the above described Heap Sort algorithm will become crystal clear.



Login to Access Content

Time Complexity:

Time complexity of heapify is O(Logn).
Time complexity of BUILD_MAX_HEAP() is O(nlog₂n).
Time complexity of Heap Sort is O(nLog₂n). n = total number of input elements.

Space Complexity:

O(1). Heap Sort is in-place.

Instructor: