Heap sort, C# - rextester

Heap sort

//Rextester.Program.Main is the entry point for your code. Don't change it.
//Compiler version 4.0.30319.17929 for Microsoft (R) .NET Framework 4.5

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;

namespace Rextester
{
    public class Program
    {
        public static void Main(string[] args) {
            /* 
            Heap sort is a comparison based sorting technique based on Binary Heap data structure. 
            It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining elementS.
            
            A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
            
            A Binary Heap is a Complete Binary Tree where items are stored in a special order such that value in a parent node is greater(or smaller) than the values in its two children nodes. 
            The former is called as max heap and the latter is called min heap. The heap can be represented by binary tree or array.
            */
            
            int [] nums = { 12, 19, 15, 8, 4, 6, 3, 29, 9, 2, 22, 44, 20, 25 };
            int n = nums.Length; 
            HeapSort ob = new HeapSort(); 
            
            Console.WriteLine("Before heap sort, the array is"); 
            ob.Display(nums);
            
            
            ob.sort(nums); 
            Console.WriteLine("Sorted array is"); 
            ob.Display(nums); 
        }
    }
    
    public class HeapSort 
    { 
 
        public void sort(int[] arr) { 
            int size = arr.Length; 
            // Build max heap (rearrange array) 
            for (int i = size / 2 - 1; i >= 0; i--) {
                heapify(arr, size, i); 
            }

Console.WriteLine("Max heap is"); 
            Display(arr);
            
            // One by one extract an element from heap 
            for (int i = size-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 
        public void heapify(int[] arr, int n, int i) { 
            int largest = i; // Initialize largest as root 
            int left = 2*i + 1; // left = 2*i + 1 
            int right = 2*i + 2; // right = 2*i + 2

// 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 != i) { 
                int swap = arr[i]; 
                arr[i] = arr[largest]; 
                arr[largest] = swap;

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

// Display the array 
        public  void Display(int []arr) { 
            int size = arr.Length; 
            for (int indx=0; indx < size; ++indx) 
                Console.Write(arr[indx] + " "); 
            Console.WriteLine(); 
        }
        
    }
    
    
}


run \| edit \| history \| help	0