Heap Sort

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. It first transforms the input array into a max-heap (where the largest element is at the root) and then repeatedly extracts the largest element, placing it at the end of the array while adjusting the heap. This process continues until the entire array is sorted.

Heap Sort has a time complexity of O(n log n) in all cases, as each “heapify” operation (adjusting the heap) runs in O(log n) and is applied to all elements. It is not a stable sort, but it is in-place, requiring only a constant amount of additional space.
 

How Heap Sort Works:

Build a Max Heap:

Arrange the elements in a binary tree structure to satisfy the max heap property, where each parent node is greater than its children.
 

Extract the Root (Maximum Element):

Remove the root element (maximum value) of the heap and swap it with the last element in the heap.
 

Re-heapify:

Restore the heap property by “heapifying” the remaining elements. This involves comparing the new root with its children and swapping if necessary, then recursively heapifying the affected subtree.
 

Repeat Extraction:

Repeat the process of extracting the root and re-heapifying until all elements are sorted.
 

End Condition:

The algorithm completes when all elements are extracted from the heap and placed in their correct positions in the array.
 

 
Time Complexity:

Best Case: O(n log n), when the input array is already a valid heap.

Average Case: O(n log n), because heap operations (insertion and extraction) take O(log n) time, and we perform these operations n times.

Worst Case: O(n log n), because the worst-case scenario still involves n extractions and reheapifications, and each heap operation (insertion or extraction) takes O(log n) time.

 
Space Complexity:

O(1), because Heap Sort is an in-place sorting algorithm.
 

 

using System;

namespace Heap_sort
{
    public class MainClass
    {
        public static void Main(string[] args)
        {
            int[] mykeys = new int[] { 2, 5, -4, 11, 0, 18, 22, 67, 51, 6 };

            //double[] mykeys = new double[] {2.22, 0.5, 2.7, -1.0, 11.2};  

            //string[] mykeys = new string[] {"Red", "White", "Black", "Green", "Orange"};  

            Console.WriteLine("\nOriginal Array Elements:");
            printArray(mykeys);

            heapSort(mykeys);

            Console.WriteLine("\n\nSorted Array Elements:");
            printArray(mykeys);
            Console.WriteLine("\n");
            Console.ReadLine();
        }

        private static void heapSort<T>(T[] array) where T : IComparable<T>
        {
            int heapSize = array.Length;

            buildMaxHeap(array);

            for (int i = heapSize - 1; i >= 1; i--)
            {
                swap(array, i, 0);
                heapSize--;
                sink(array, heapSize, 0);
            }
        }

        private static void buildMaxHeap<T>(T[] array) where T : IComparable<T>
        {
            int heapSize = array.Length;

            for (int i = (heapSize / 2) - 1; i >= 0; i--)
            {
                sink(array, heapSize, i);
            }
        }

        private static void sink<T>(T[] array, int heapSize, int toSinkPos) where T : IComparable<T>
        {
            if (getLeftKidPos(toSinkPos) >= heapSize)
            {
                // No left kid => no kid at all  
                return;
            }


            int largestKidPos;
            bool leftIsLargest;

            if (getRightKidPos(toSinkPos) >= heapSize || array[getRightKidPos(toSinkPos)].CompareTo(array[getLeftKidPos(toSinkPos)]) < 0) { largestKidPos = getLeftKidPos(toSinkPos); leftIsLargest = true; } else { largestKidPos = getRightKidPos(toSinkPos); leftIsLargest = false; } if (array[largestKidPos].CompareTo(array[toSinkPos]) > 0)
            {
                swap(array, toSinkPos, largestKidPos);

                if (leftIsLargest)
                {
                    sink(array, heapSize, getLeftKidPos(toSinkPos));

                }
                else
                {
                    sink(array, heapSize, getRightKidPos(toSinkPos));
                }
            }

        }

        private static void swap<T>(T[] array, int pos0, int pos1)
        {
            T tmpVal = array[pos0];
            array[pos0] = array[pos1];
            array[pos1] = tmpVal;
        }

        private static int getLeftKidPos(int parentPos)
        {
            return (2 * (parentPos + 1)) - 1;
        }

        private static int getRightKidPos(int parentPos)
        {
            return 2 * (parentPos + 1);
        }

        private static void printArray<T>(T[] array)
        {

            foreach (T t in array)
            {
                Console.Write(' ' + t.ToString() + ' ');
            }

        }
    }

}