 This lesson is for members. Join us? Get access to all 3,000+ tutorials + a community with expert developers around the world.

Unlock This Lesson
1×
Become a member
to unlock all features Level Up!

Access all courses & lessons on egghead today and lock-in your price for life.

Autoplay

Implement the Heapsort algorithm using TypeScript / JavaScript TypeScript
^2.1.4

Once you are familiar with the Heap data structure, a number of programming challenges can magically become super simple. Sorting is just one of those challenges.

In this lesson we cover the heap sort algorithm, why is it called heap sort and how to implement it using JavaScript / TypeScript. Code You must be a Member to view code

Access all courses and lessons, track your progress, gain confidence and expertise.

Become a Member
and unlock code for this lesson Discuss Transcript

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.