HeapSort

HeapSort

using System;

namespace HeapSort
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var input = new int[]{4, 7, 1, 9, 8};
            
            Console.WriteLine("Input:");
            display(input);
            
            heapSort(input);
                       
            Console.WriteLine("Sorted Output:");
            display(input);
        }
        
        static void display(int[] arr) {
            foreach (var item in arr) {
                Console.Write(item + " ");
            }
            Console.WriteLine(" ");
        }
        
        static void heapSort(int[] input) {
            buildMaxHeap(input);
            
            Console.WriteLine("Max heap is");
            display(input);
           
            int end = input.Length - 1;
            while (end > 0) {
                int temp = input[0];
                input[0] = input[end];
                input[end] = temp;
                
                end--;
                
                heapify(input, 0, end);
            }
        }
        
        // Given that Left(i) and Right(i)
        // are already max heaps, position 'i' at the 
        // correct place
        static void heapify(int[] input, int i, int length) {
            
            int left = 2 * i + 1;
            int right = 2 * i + 2;
             
            int largest = i;
            if ((left <= length) && (input[left] > input[i])) {
                largest = left;
            }    
            
            if ((right <= length) && (input[right] > input[largest])) {
                largest = right;
            }
            
            if (i != largest) {
                int temp = input[i];
                input[i] = input[largest];
                input[largest] = temp;
                
                heapify(input, largest, length);
            }
        }
        
        static void buildMaxHeap(int[] input) {
            int count = input.Length - 1;
            for(int i = count / 2; i >= 0; i--) {
                heapify(input, i, count);
            }
        }
    }
}