Understanding Heap Sort with JavaScript
What is Heap Sort?
Heap Sort is a comparison-based sorting technique that sorts elements using Almost Complete Binary Tree.
Heap Sort is considered better than quicksort in worst case as its time complexity is O(nlogn) which is better than O(n²) of quicksort. You may ask what is an almost complete binary tree on which heap sort is performed. Let us understand that first.
What is Almost Complete Binary Tree?
A binary tree is almost complete if it satisfies the following conditions -
1.Each node should have left child first before having right child. That is, no node can have only right child without having left child.
2.Each level of the tree should be complete before moving on to the next level.
Notice above that both conditions are satisfied.
In the above tree, the second condition is not satisfied as this tree has a third level before completing the second level (parent node does not have the right child).
Now, the almost complete binary tree should be either max-heap or min-heap to perform sorting.
What is max-heap?
An almost complete binary tree in which the parent node is always greater than its children is called a max-heap.
Consider an example below in which each parent is greater than its children.
Note the max-heap is not sorted yet, if we represent it in an array you will understand better.
What is min-heap?
An almost complete binary tree in which parent node is always smaller than its children is called a min-heap.
Consider the example below —
If we want to sort elements in decreasing order then we can easily do so with a min-heap and if we want to sort them in an increasing order then max-heap can easily do so.
Performing heap sort
First, we need to construct a max-heap or min-heap from an almost complete binary tree. We are going to construct max-heap here so that elements can be sorted in increasing order. Let's call building max-heap as a max-heapify process.
1. Building max-heap
To construct max-heap, the last parent which is present at (n/2)-1 position(n is the total number of elements) is compared with its children.
Voila!! We now have a max-heap —
JavaScript code for building max-heap
Time Complexity for max-heapify
The time complexity to build max-heap is O(n). Time complexity depends on the number of swaps and comparisons made. As we started building max-heap from index 2 therefore loop runs for n/2 times. For the elements at 1 and 2 index, two comparisons are made with each of their children but only one swap is performed for them. Therefore, for one swap there are two comparisons as the loop runs n/2 times therefore for n/2 swaps there are n comparisons. Therefore Time Complexity = O(n/2 +n) = O(n).
2. Deleting the root element
The heap is still not sorted. To sort elements in ascending order we need to remove the largest element and place it at the last position and keep on doing that till we get sorted elements.
So here 50 is removed and then the last element is placed at its position.
The heap obtained is not a max-heap therefore we need to max-heapify it again.
Time Complexity of delete step
This step takes O(1) time as we are just swapping the last element and the root element.
3. Fixing the max-heap
The process of deleting the root element and then performing max-heapify is repeated until we get a sorted array of elements. This is done n times as there is n number of elements.
Time Complexity for fixing max-heap
As we are moving in only one path of the tree of height logn to get the max-heap again, therefore, its time complexity is O(log n)
JavaScript code for heap sort
Time Complexity of Heap Sort
The time complexity is divided into two steps —
1. Max-heapify — O(n)
2. n times-
a) Deletion — O(1)
b) Max-heapify — O(log n)
=O(n + n*O(logn)) = O(nlogn)
That’s it, we are done!!If you want to look at the code refer here.
I hope it was understandable. If you liked the article do follow for more.
References
[1] Wikipedia
[2] GeeksforGeeks
