Heap Sort

We explained heap and priority queue in one of our previous posts which you can check here. We will describe how heap sort algorithm works based on what we have learned about heap data structure. If you remember heap data structure is a complete binary tree which satisfies the heap properties of min or max heap. We also saw that we can easily represent a binary heap with an array data structure on which we can perform various operations in order to convert it to heap. One of those operations was heapify operation which rearranges the elements of the array so it satisfies the properties of heap. Having said that in order to sort the elements of a given array we will use the exact same operation of heap data structure in order to sort the array. We can break the algorithm to 4 steps.

1. Take the input array and convert it to max heap by applying heapify operation on it.
2. Take the root (first) element as it is the max element now and swap it with the last element in the array. Now the last element is the largest of all and it is in the correct place.
3. Heapify the array again without already sorted elements at the end of the array because they are already in the correct position.
4. Repeat steps 1 to 3 for all remaining elements in the unsorted imaginary sub array.

1

2

3

Implementation

Let’s implement the steps explained above with a C# code.

First we will need a heapify method with which we are already familiar from our previous article.

        private static void Heapify(int[] arr, int index, int length)
        {
            int largestInd = index;

            int left = 2 * index + 1;
            int right = 2 * index + 2;

            if (left < length && arr[left] > arr[largestInd])
            {
                largestInd = left;
            }

            if (right < length && arr[right] > arr[largestInd])
            {
                largestInd = right;
            }

            if (largestInd != index)
            {
                var temp = arr[index];
                arr[index] = arr[largestInd];
                arr[largestInd] = temp;

                Heapify(arr, largestInd, length);
            }
        }

With a help of this method we will implement HeapSort method

        private static void HeapSort(int[] arr)
        {
            var n = arr.Length;

            //First convert the array to max heap
            for (int i = n / 2 - 1; i >= 0; i--)
            {
                Heapify(arr, i, n);
            }

            // Starting from the last element
            // swap last and first element as the
            // first element will be always the max element
            // then reduce the index (array size)
            for (int j = n-1; j >= 0; j--)
            {
                int temp = arr[j];
                arr[j] = arr[0];
                arr[0] = temp;
                // Heapify the remaining elements
                // pay attention to j index we pass to Hepify method
                Heapify(arr, 0, j);
            }
        }

Let’s now test our heapsort method

        static void Main(string[] args)
        {
            int[] arr = { 25, 10, 40, 1, 15 };

            HeapSort(arr);

            PrintArr(arr);

            Console.ReadLine();
        }

        private static void PrintArr(int[] arr)
        {
            string space = "";
            foreach (var i in arr)
            {
                Console.Write(space + i);
                space = ",";
            }

            Console.WriteLine("\n");
        }

And the output is:

1,10,15,25,40

HeapSort has a complexity of O(nlog n) in all cases and it has O(1) space complexity as it operates on the same array all the time.