Heap Sort, the second daughter of the family, has a busy life.  

As the owner of a local, well-liked restaurant, Heap Sort's Heaping Helpings, she is constantly running around trying to make her restaurant better. As the mom of four kids, she (and husband Cocktail Shaker Sort) are constantly trying to stay one step ahead of their childrens' antics, not always with success.

Apple pie on black board
Photo by Hugo Aitken / Unsplash

Heap Sort is nearly the exact opposite of her mother Merge Sort. She's a fantastic chef and her pies are legendary around town. Moreover, she absolutely adores cooking for other people, and has offered to teach her dear Mom a thing or two (she politely declined). Because of her success, the family regards her as the star child, much to older sister Insertion Sort's annoyance.

Top view of fruit pies and a coffee pot
Photo by Brooke Lark / Unsplash

Heap Sort has a good life, and she knows it. Busy, yes; but then again, who isn't?

The Rundown

exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound

Algorithm

  1. CONSTRUCT a "max" heap from the unsorted data that satisfies the heap property.
  2. SWAP the first and final elements.  The final element is now sorted.
  3. DECREMENT the range of "considered" elements (those still needing to be sorted) by 1.
  4. RESTRUCTURE the heap to satisfy the heap property (again).
  5. SWAP the new root with the last item in the range of considered items.
  6. CONTINUE until the range of considered items is 1.

Visualization

This is one of the more complication visualizations in this series.  I'm going to break it down into two steps.

Step 1: Satisfy Heap Property

The unsorted chart looks like this:

In order to even use Heap Sort, we must first satisfy something known as the heap property. The heap property (for a "max heap", which is what we will use in this post) is:

"For any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C"

The problem with the collection above is that the nodes do not satisfy this property; the value at the beginning (or "top") of the list is not the highest value. To make the property true, the algorithm sorts the collection into the following:

Now this collection satisfies the heap property: for any node C which has a parent P (a "parent" here meaning "appears earlier in this list"), said parent P has a value greater than C. This is what the next image in the animation is trying to convey:

This diagram is an outline of the heap, and the tree structure it represents. Because we now have a fully-balanced heap, we can proceed to the next step.

Step 2: Swap and Rebuild

At this point, we know that the "root" of the heap (e.g. the node in the first position) must be the highest value in the considered range. Therefore we can place it at the "back" of the list.

We must then decrease the considered range by 1 (so as not to include the just-sorted item) and rebuild the heap. We continue to do this until the considered range is 1, at which point, the collection will be sorted.

You should also check out this "audibilization" of this algorithm from YouTube:

C# Implementation

public class HeapSort
{
    static void Sort(int[] array)
    {
        var length = array.Length;
        for (int i = length / 2 - 1; i >= 0; i--)
        {
            Heapify(array, length, i);
        }
        for (int i = length - 1; i >= 0; i--)
        {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            Heapify(array, i, 0);
        }
    }

    //Rebuilds the heap
    static void Heapify(int[] array, int length, int i)
    {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < length && array[left] > array[largest])
        {
            largest = left;
        }
        if (right < length && array[right] > array[largest])
        {
            largest = right;
        }
        if (largest != i)
        {
            int swap = array[i];
            array[i] = array[largest];
            array[largest] = swap;
            Heapify(array, length, largest);
        }
    }

    public static void Main()
    {
        int[] arr = { 74, 19, 24, 5, 8, 79, 42, 15, 20, 53, 11 };
        Console.WriteLine("Heap Sort");

        CommonFunctions.PrintInitial(arr);

        Sort(arr);

        CommonFunctions.PrintFinal(arr);

        Console.ReadKey();
    }
}

Time and Space Complexity

Heap sort is a consistent algorithm: the best, average, and worse-case time complexities are all O(n log n). In fact, heap sort is one of the most commonly used sorting algorithms in the real-world. Its efficient time complexity and low space requirements make it a good candidate for implementation in our apps.

Summary

The goodness that is Heap Sort knows no bounds; it is an efficient algorithm that is in use today in production systems. If you're looking to be to sort large lists, Heap Sort just might be your best option. Plus, she makes a mean rhubarb pie.

Need a drink? So does the next algorithm at the reunion, Cocktail Shaker Sort!

Cocktail Shaker Sort in C#
Cocktail Shaker Sort would like a drink. A strong one, if you please. The father of four rambunctious children and husband to the always-working HeapSort, “Shaky” (a loving nickname for him which is never said to his face) is astay-at-home dad who absolutely adores his children but just wants so…
Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!