Want more egghead?

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

Already subscribed? Sign In

Autoplay

    Implement the Heapsort algorithm using TypeScript / JavaScript

    Basarat Ali SyedBasarat Ali Syed

    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.

    typescriptTypeScript
    Code

    Code

    Become a Member to view 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
    Transcript

    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.

    Discuss

    Discuss