C# Implementation of Heap Sort

The code create the maxheap of the given array of size N and then swap the 0th index (max value) with the last index (N-1) and then again create maxheap with reduced array of size (N-1).

Continue this process unless complete array is sorted.

	public class MyHeap
	{
	private int[] arr;
	private int size;
	public MyHeap(int[] a)
	{
	arr = a;
	size = a.Length;
	}
	public void HeapSort()
	{
	int length = size;
	for (int i = length; i > 0; i--)
	{
	Heapify(i);
	swap(0, i - 1);
	}
	}
	private void Heapify(int length)
	{
	for (int i = length / 2; i >= 0; i--)
	{
	MaxHeapify(i, length);
	}
	}
	private void MaxHeapify(int startIndex, int count)
	{
	int largest = startIndex;
	int l = 2*startIndex + 1;
	int r = 2*startIndex + 2;
	if (l < count && arr[l] > arr[largest])
	{
	largest = l;
	}
	if (r < count && arr[r] > arr[largest])
	{
	largest = r;
	}
	if (largest != startIndex)
	{
	swap(largest, startIndex);
	}
	}
	private void swap(int a, int b)
	{
	int temp = arr[a];
	arr[a] = arr[b];
	arr[b] = temp;
	}
	}

view raw gistfile1.txt hosted with ❤ by GitHub