Heap Sort program in C#

Heap sort is a comparison-based sorting algorithm that uses the binary heap data structure. It is an efficient algorithm with a time complexity of O(n log n) and is considered an in-place sorting algorithm. Heap sort works by first building a max heap from the array and then repeatedly extracting the maximum element from the heap and placing it at the end of the sorted array.

Here's an explanation of the heap sort algorithm step by step:

1. Build a max heap: Starting from the first non-leaf node (index n/2 - 1), heapify the array by comparing each node with its children and swapping if necessary to maintain the max heap property. Repeat this process for all non-leaf nodes until the entire array is a max heap.
2. Extraction: Repeatedly extract the maximum element from the max heap. Swap it with the last element of the heap, reduce the size of the heap by one, and heapify the remaining elements to maintain the max heap property. Repeat this process until the heap is empty.
3. At the end of the process, the array will be sorted in ascending order.

using System;

public class HeapSort
{
    public static void Main()
    {
        int[] arr = { 64, 25, 12, 22, 11 };

        Console.WriteLine("Original array:");
        PrintArray(arr);

        Sort(arr);

        Console.WriteLine("Sorted array:");
        PrintArray(arr);
    }

    public static void Sort(int[] arr)
    {
        int n = arr.Length;

        // Build max heap
        for (int i = n / 2 - 1; i >= 0; i--)
        {
            Heapify(arr, n, i);
        }

        // Extract elements from the max heap
        for (int i = n - 1; i >= 0; i--)
        {
            // Move current root (maximum element) to the end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // Heapify the reduced heap
            Heapify(arr, i, 0);
        }
    }

    public static void Heapify(int[] arr, int n, int rootIndex)
    {
        int largest = rootIndex; // Initialize largest as root
        int left = 2 * rootIndex + 1; // Left child
        int right = 2 * rootIndex + 2; // Right child

        // If left child is larger than root
        if (left < n && arr[left] > arr[largest])
        {
            largest = left;
        }

        // If right child is larger than largest so far
        if (right < n && arr[right] > arr[largest])
        {
            largest = right;
        }

        // If largest is not root
        if (largest != rootIndex)
        {
            // Swap the root with the largest element
            int temp = arr[rootIndex];
            arr[rootIndex] = arr[largest];
            arr[largest] = temp;

            // Recursively heapify the affected sub-tree
            Heapify(arr, n, largest);
        }
    }

    public static void PrintArray(int[] arr)
    {
        foreach (int num in arr)
        {
            Console.Write(num + " ");
        }
        Console.WriteLine();
    }
}

In this example, the Sort method implements the heap sort algorithm. The Main method initializes an array, calls the Sort method to sort the array, and then prints both the original and sorted arrays using the PrintArray method.

Original array:
64 25 12 22 11 
Sorted array:
11 12 22 25 64 

The program demonstrates the step-by-step execution of the heap sort algorithm on the given array and outputs the sorted array.

Heap sort is an efficient sorting algorithm, but it requires additional space for the heap data structure. It is commonly used in practice and is particularly useful when a stable sorting algorithm is not required.