Heapsort in C#

Heap.cs

/*
* Created by SharpDevelop.
* Date: 8/15/2013
* Time: 6:33 PM
*
 *
 */
using System;
using System.Collections.Generic;
 
namespace Utility
{
                /// <summary>
                /// A max-heap
                /// </summary>
                public class Heap<T>
                {
                                /// <summary>
                                /// Used to compare elements to be sorted
                                /// </summary>
                                private Comparison<T> comparer;
                               
                                /// <summary>
                                /// Internal list on which the heap is based
                                /// </summary>
                                public List<T> InternalList;
                               
                                /// <summary>
                                /// Length of the heap
                                /// </summary>
                                public int Length { get; set; }
                               
                                public Heap(List<T> inputList, Comparison<T> comparer)
                                {
                                                InternalList = inputList;
                                                Length = inputList.Count;
                                                this.comparer = comparer;
                                                                                               
                                                //Build a max-heap from the input list
                                                BuildMaxHeap();
                                }
                               
                                /// <summary>
                                /// Returns index of parent of the element at index i
                                /// </summary>
                                /// <param name="i"></param>
                                private int Parent(int i)
                                {
                                                return i / 2;
                                }
                               
                                /// <summary>
                                /// Returns index of left child of the element at index i
                                /// </summary>
                                /// <param name="i"></param>
                                private int Left(int i)
                                {
                                                return 2 * i;
                                }
                               
                                /// <summary>
                                /// Returns index of right child of the element at index i
                                /// </summary>
                                /// <param name="i"></param>
                                private int Right(int i)
                                {
                                                return (2 * i) + 1;
                                }
                               
                                /// <summary>
                                /// Swaps elements at index i and j with each other
                                /// </summary>
                                /// <param name="i"></param>
                                /// <param name="j"></param>
                                public void Swap(int i, int j)
                                {
                                                T temp = InternalList[i];
                                                               
                                                InternalList[i] = InternalList[j];
                                                InternalList[j] = temp;
                                }
                               
                                /// <summary>
                                /// Builds a max-heap (without using recursion to heapify child trees)
                                /// </summary>
                                /// <param name="i"></param>
                                public void SequentialMaxHeapify(int root)
                                {             
                                                bool heapified = false;
                                               
                                                while(!heapified)
                                                {                                             
                                                                int largest;
                                                                int l = Left(root);
                                                                int r = Right(root);
                                                               
                                                                //Check if left child exists and if it is larger than the root
                                                                if(l < Length && comparer(InternalList[l], InternalList[root]) > 0)
                                                                {
                                                                                largest = l;
                                                                }
                                                                //If not then we assume that the root is largest
                                                                else
                                                                {
                                                                                largest = root;
                                                                }
                                                               
                                                                //Now compare largest of left child or parent with the right child,
                                                                //find the largest of the three
                                                                if(r < Length && comparer(InternalList[r], InternalList[largest]) > 0)
                                                                {
                                                                                largest = r;
                                                                }
                                                               
                                                                //If largest is not the root then we need to switch
                                                                if(largest != root)
                                                                {
                                                                                Swap(root, largest);
                                                                               
                                                                                //On next loop start from largest child as swap might have resulted
                                                                                //in child
                                                                                root = largest;
                                                                }
                                                                else
                                                                {
                                                                                heapified = true;
                                                                }
                                                }
                                }
                               
                                /// <summary>
                                /// Builds a max-heap (assumes that left and right child of i
                                /// are already max-heaps)
                                /// </summary>
                                /// <param name="i"></param>
                                public void MaxHeapify(int i)
                                {
                                                int largest;
                                                int l = Left(i);
                                                int r = Right(i);
                                               
                                                //Check if left child exists and if it is larger than the root
                                                if(l < Length && comparer(InternalList[l], InternalList[i]) > 0)
                                                {
                                                                largest = l;
                                                }
                                                //If not then we assume that the root is largest
                                                else
                                                {
                                                                largest = i;
                                                }
                                               
                                                //Now compare largest of left child or parent with the right child,
                                                //find the largest of the three
                                                if(r < Length && comparer(InternalList[r], InternalList[largest]) > 0)
                                                {
                                                                largest = r;
                                                }
                                               
                                                //If largest is not the root then we need to switch
                                                if(largest != i)
                                                {
                                                                Swap(i, largest);
                                                               
                                                                //Swap might have caused the child to lose its max-heap property so perform
                                                                //a recursive call
                                                                MaxHeapify(largest);
                                                }
                                }
                               
                                /// <summary>
                                /// Builds a max-heap from an unordered input list
                                /// </summary>
                                public void BuildMaxHeap()
                                {
                                                //Start from the left-most parent element in the heap
                                                //Everything after this are leaf nodes
                                                int i = Length/2;
                                               
                                                while(i >= 0)
                                                {
                                                                MaxHeapify(i);
                                                               
                                                                i--;
                                                }
                                }
                }
}

HeapSorter.cs

/*
* Created by SharpDevelop.
* Date: 8/15/2013
* Time: 6:22 PM
*
 *
 */
using System;
using System.Collections.Generic;
 
namespace Utility
{
                /// <summary>
                /// An implementation of the heapsort algorithm
                /// </summary>
                public class HeapSorter : ISorter
                {
                                /// <summary>
                                /// Sorts an input list using the heapsort algorithm
                                /// </summary>
                                /// <param name="inputList"></param>
                                /// <returns></returns>
                                public List<T> Sort<T>(List<T> inputList, Comparison<T> comparer)
                                {
                                                Heap<T> heapObj = new Heap<T>(inputList, comparer);
                                               
                                                for(int i = inputList.Count - 1; i >= 0; i--)
                                                {
                                                                //Swap top of heap with last element
                                                                heapObj.Swap(0, i);
                                                               
                                                                //Decrease the length of the heap to exclude top element
                                                                heapObj.Length--;
                                                               
                                                                //Re-build the heap (ignoring the last few elements
                                                                //due to decreased length)
                                                                heapObj.MaxHeapify(0);
                                                }
                                               
                                                return heapObj.InternalList;
                                }
                }
}

ISorter.cs

/*
* Created by SharpDevelop.
* Date: 8/15/2013
* Time: 6:17 PM
*
 *
 */
using System;
using System.Collections.Generic;
 
namespace Utility
{
                /// <summary>
                /// Defines an interface for a sorting algorithm
                /// </summary>
                public interface ISorter
                {
                                List<T> Sort<T>(List<T> inputList, Comparison<T> comparer);
                }
}