- 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.

Advertisements