Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
2.1 kB
1
Indexable
Never
using System;

class HeapSort
{
    public static void Heapify(int[] array, int n, int i)
    {
        int largest = i; // Initialize largest as root
        int leftChild = 2 * i + 1; // Left child
        int rightChild = 2 * i + 2; // Right child

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

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

        // If largest is not root
        if (largest != i)
        {
            // Swap array[i] and array[largest]
            int temp = array[i];
            array[i] = array[largest];
            array[largest] = temp;

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

    public static void HeapSortFunction(int[] array)
    {
        int n = array.Length;

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

        // One by one extract an element from heap
        for (int i = n - 1; i >= 0; i--)
        {
            // Move current root to end
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;

            // Call max heapify on the reduced heap
            Heapify(array, i, 0);
        }
    }

    static void Main()
    {
        int[] array = { 12, 11, 13, 5, 6, 7 };

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

        HeapSortFunction(array);

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

    public static void PrintArray(int[] array)
    {
        int n = array.Length;
        for (int i = 0; i < n; ++i)
        {
            Console.Write(array[i] + " ");
        }
        Console.WriteLine();
    }
}
Leave a Comment