Implement the Heapsort algorithm using TypeScript / JavaScript

Consider the simple array of items 9, 4, 2, 7, 5, 3. Our task is to sort these in ascending order. We can simplify this task as simple repeated extractions of the minimum item from the set. If we do that, we get the sorted result 2, 3, 4, 5, 7, 9, in ascending order.

We already know an amazing data structure called, "The heap," that is great for the specific problem of repeated minimum competitions. Let's cored up heap sort using the heap data structure. We start off by bringing the heap class and the compare function from the code we wrote in our heap lesson.

Next, we create our heap sort function that takes an array of type T along with the comparison function and simply returns the sorted array. We create a heap based on the past and comparison function. Next, we push each item into the heap. We prepare the result array. Loop n times once more. In each iteration, we extract the root from the heap and put it on the result.

Finally, we return the result and that's it. Let's try it out on our example. We simple console log out the result of heap sorting or example input array. As you can see, it works as expected. Now, let's analyze the time complexity of algorithm.

In our code, we loop through the input array, and in each iteration we simply add the item into the heap, resulting in a time complexity of this section being the complexity of the add operation which is log n times the number iterations which is n. In total, n log n.

In the second loop, we call extract root n times, so the time complexity is n times the complexity of extract root. Again, the total for this section is n times log n. Therefore, the total complexity of heap sort is of the order n log n.

As you can see, simply using the heap data structure has given us the best asymptotic time performance for comparison-based sorting.