How to Implement Heap Sort in C#

This following article explains how to implement Heap Sort in C#.

What is Heap Sort?

In brief, Heap sort is a comparison-based sorting algorithm that sorts an array by using a binary heap data structure. Moreover, it’s an efficient and stable sorting algorithm. Evidently, it has a time complexity of O(n log n).

Actually, the algorithm works by dividing the input array into two parts: the sorted part and the unsorted part. Further, the sorted part is built up at the end of the array while the unsorted part is reduced towards the beginning of the array. Then, the algorithm repeatedly selects the maximum element from the unsorted part of the array. After that, it moves it to the end of the sorted part. Meanwhile, the process continues until the unsorted part is empty.

As a matter of fact, Heap sort is a useful sorting algorithm for sorting arrays of numbers or other comparable objects. However, it’s not as widely used as other sorting algorithms like quicksort or merge sort. Still it has its own advantages. To that end, it returns a guaranteed O(n log n) performance. Most important feature of Heap Sort is its ability to sort elements that are not in a contiguous memory block. The following code shows its implementation in C#.

Implementation of Heap Sort in C#

using System;

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

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            Heapify(arr, 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 = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

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

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    static void Heapify(int[] arr, int n, int i)
    {
        int largest = i;  // Initialize largest as root
        int l = 2 * i + 1;  // left = 2*i + 1
        int r = 2 * i + 2;  // right = 2*i + 2

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

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

        // If largest is not root
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

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

class Program
{
    static void Main(string[] args)
    {
        int[] arr = {12, 11, 13, 5, 6, 7};
        int n = arr.Length;

        HeapSort.Sort(arr);

        Console.WriteLine("Sorted array is:");
        for (int i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
    }
}

Output

Further Reading

Parameter and ParameterCollection in ADO.NET

Database Manipulation Using DataGrid

Code Render Block in ASP.NET

ASP.NET Practice Exercise

• Angular
• ASP.NET
• C
• C#
• C++
• CSS
• Dot Net Framework
• HTML
• IoT
• Java
• JavaScript
• Kotlin
• PHP
• Power Bi
• Python
• Scratch 3.0
• TypeScript
• VB.NET

Princites