Heapsort in C#

  • 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s