InstructorBasarat Ali Syed

Published 7 years ago

Updated 3 years ago

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.

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.

egghead

~ 8 minutes ago

Markdown supported.

Become a member to join the discussionEnroll Today

Member comments are a way for members to communicate, interact, and ask questions about a lesson.

The instructor or someone from the community might respond to your question Here are a few basic guidelines to commenting on egghead.io

Be on-TopicComments are for discussing a lesson. If you're having a general issue with the website functionality, please contact us at support@egghead.io.

Avoid meta-discussionCode Problems?Should be accompanied by code! Codesandbox or Stackblitz provide a way to share code and discuss it in context

Details and ContextVague question? Vague answer. Any details and context you can provide will lure more interesting answers!