Heap Sort Algorithm in C#

1. Introduction

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure. The basic idea behind Heap Sort is to transform the input array into a max-heap structure. The largest value (found at the root) is then swapped with the last item of the heap followed by a heapify process to restore the max-heap property. This procedure is repeated for the heap's reduced size.

2. Implementation Steps

1. Build a max-heap from the input data.

2. The largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of the heap by one.

3. Repeat the above step until the size of the heap is one.

3. Implementation in C#

using System;
public class HeapSort {
    // This function takes an array and heapifies a subtree rooted with node i
    public static void Heapify(int[] arr, int n, int i) {
        int largest = i;  // Initialize largest as root
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest])
            largest = left;
        if (right < n && arr[right] > arr[largest])
            largest = right;
        if (largest != i) {
            // Swap arr[i] and arr[largest]
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;
            // Recursively heapify the affected sub-tree
            Heapify(arr, n, largest);
        }
    }
    // Main function to do heap sort
    public static void Sort(int[] arr) {
        int n = arr.Length;
        // Build a max heap
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, n, i);
        // Extract elements from heap one by one
        for (int i = n - 1; i >= 0; i--) {
            // Move the current root to the end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            // Call max heapify on the reduced heap
            Heapify(arr, i, 0);
        }
    }
}
public class Program {
    public static void Main() {
        int[] arr = {12, 11, 13, 5, 6, 7};
        Console.WriteLine("Unsorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
        HeapSort.Sort(arr);
        Console.WriteLine("\nSorted array:");
        foreach (var item in arr) {
            Console.Write(item + " ");
        }
    }
}

Output:

Unsorted array:
12 11 13 5 6 7
Sorted array:
5 6 7 11 12 13

Explanation:

1. HeapSort is a class that houses the logic for the heap sort algorithm.

2. The Heapify function is the heart of the algorithm. It ensures that the subtree with root at a given index i is a max-heap.

3. The Sort function first constructs a max-heap from the given array. After building the max-heap, the largest value is placed at the end of the array by swapping it with the last item in the heap, and the heap size is reduced by one.

4. The process of placing the root at the end of the array and reducing the heap size is repeated until the entire array is sorted.

5. The Program class contains the Main method that demonstrates how the HeapSort class can be used to sort an integer array.