- Building the heap takes O(n)
- Sorting using the heap takes O(nlogn)
- Sorts in place (useful when space is critical)
- Not used often in production because of poor cache performance (does not compare array elements which are close by)
- Used in construction of priority queues (job scheduling)

Firstly, we implement a heap data structure. I included the traditional (and easy to understand) recursive version of MaxHeapify() as well a sequential version.

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--;
}
}
}
}

The actual heapsort algorithm implementation is small:

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;
}
}
}

The sorter class is used as follows:

HeapSorter sorter = new HeapSorter();
List<int> outputList = sorter.Sort(inputList, (x, y) => x.CompareTo(y));

The second argument is a lambda expression that matches the inbuilt delegate Comparison<T>. It tells the generic sorter how to compare two elements of class T. We’re sorting just integers here but if we were sorting a class of Person the Comparison<T> delegate might look as follows if we wanted to sort by age:

HeapSorter sorter = new HeapSorter();
List<Person> outputList = sorter.Sort(inputList, (x, y) => x.Age.CompareTo(y.Age));

The entire code is available here.