Continuing with my C# Algorithms series, I’ve just completed a rather lengthy effort to implement and test min and max heap algorithms, including heap sort, along with a priority queue, something not provided by the BCL. While the heap sort is not always the most efficient, the algorithms required to accomplish the sort, specifically the heap data structure functions, supply the requisite functionality to make the implementation of a priority based queue quite easy to implement.
This work is a part of my continuing effort to work through all of the common algorithms found in Introduction to Algorithms 3rd Edition, I highly recommend this work to anyone who wishes to study classic computer science algorithms. For me, the exercise of implementing them in C# is a great learning experience.
First, let’s look at how it works. You have a job scheduler that needs to execute jobs in order of priority but jobs are enqueued with different priorities but need to be dequeued according to that priority. Here’s the Job class. Note the implementation of the MinValue and MaxValue which is needed for the heap based ordering required after a dequeue.
public class Job : IComparable
{
public string JobId { get; set; }
public double Priority { get; set; }
public int CompareTo(object obj)
{
var other = obj as Job;
if (null == other) return 1; //null is always less
return this.Priority.CompareTo(other.Priority);
}
private static Job _min;
private static Job _max;
public static Job MinValue
{
get
{
if (_min == null)
{
_min = new Job { JobId = null, Priority = double.MinValue };
}
return _min;
}
}
public static Job MaxValue
{
get
{
if (_max == null)
{
_max = new Job { JobId = null, Priority = double.MaxValue };
}
return _max;
}
}
}
And now here’s the test code that demonstrates the use of PriorityQueue<T> with the Job class.
[TestMethod]
public void JobTest()
{
IList<Job> jobs = new List<Job>
{
new Job { JobId = "test1", Priority = 45.0 },
new Job { JobId = "test2", Priority = 25.0 },
new Job { JobId = "test3", Priority = 4.0 },
new Job { JobId = "test4", Priority = 88.0 },
new Job { JobId = "test5", Priority = 96.0 },
new Job { JobId = "test6", Priority = 18.0 },
new Job { JobId = "test7", Priority = 101.0 },
new Job { JobId = "test8", Priority = 7.0 }
};
var jobQueue = new PriorityQueue<Job>(jobs, PriorityOrder.Max);
jobQueue.Enqueue(new Job
{
JobId = "test8",
Priority = 232.0
},
// min and max needed for MaxInsert or MinInsert
Job.MinValue, Job.MaxValue);
Assert.IsTrue(jobQueue.Count == 9);
var val = jobQueue.Dequeue();
Assert.IsTrue(val.Priority == 232.0);
Assert.IsTrue(jobQueue.Count == 8);
Assert.IsTrue(jobQueue.Size == 9); //heapSize not same
val = jobQueue.Peek();
Assert.IsTrue(val.Priority == 101.0);
jobQueue.TrimExcess();
Assert.IsTrue(jobQueue.Count == jobQueue.Size);
}
I’m posting the PriorityQueue<T> class here along with the static Heap class that provides the underlying heap structure algorithms. I hope you get some use out of them.
public class PriorityQueue<T> : IEnumerable<T>,
ICollection, IEnumerable where T : IComparable
{
private readonly PriorityOrder _order;
private readonly IList<T> _data;
private int _heapSize = 0;
public PriorityQueue(PriorityOrder order)
{
_data = new List<T>();
_order = order;
}
public PriorityQueue(IEnumerable<T> data, PriorityOrder order)
{
_data = data as IList<T>;
if (_data == null) _data = new List<T>(data);
_order = order;
_heapSize = _data.Count;
if (_order == PriorityOrder.Max)
Heap.BuildMaxHeap(_data);
else
Heap.BuildMinHeap(_data);
}
public PriorityQueue(int initialCapacity, PriorityOrder order)
{
_data = new List<T>(initialCapacity);
_order = order;
}
public void Clear()
{
_data.Clear();
}
public bool Contains(T item)
{
if (_order == PriorityOrder.Max)
return Heap.MaxContains(_data, item, 0, _heapSize);
else
return Heap.MinContains(_data, item, 0, _heapSize);
}
public T Dequeue()
{
if (_heapSize == 0) throw new InvalidOperationException();
if (_order == PriorityOrder.Max)
return Heap.ExtractMax(_data, _heapSize--);
else
return Heap.ExtractMin(_data, _heapSize--);
}
public void Enqueue(T item, T minItem, T maxItem)
{
if (_order == PriorityOrder.Max)
Heap.MaxInsert(_data, item, maxItem, _heapSize++);
else
Heap.MinInsert(_data, item, minItem, _heapSize++);
}
public T Peek()
{
return _data[0];
}
public void TrimExcess()
{
// trim remove items in _data beyond _heapSize
while (_heapSize < _data.Count)
{
_data.RemoveAt(_data.Count - 1);
}
}
public T[] ToArray()
{
return _data.ToArray();
}
public IEnumerator<T> GetEnumerator()
{
return _data.GetEnumerator();
}
IEnumerator IEnumerable.GetEnumerator()
{
return _data.GetEnumerator();
}
public void CopyTo(Array array, int index)
{
_data.CopyTo((T[])array, index);
}
public int Count
{
get { return _heapSize; }
}
public int Size
{
get { return _data.Count; }
}
public bool IsSynchronized
{
get { return false; }
}
public object SyncRoot
{
get { return _data; }
}
}
And here’s the Heap code. Not light reading. For help in walking through the code, review the unit tests on GitHub.
public static class Heap
{
/* What a max heap looks like from 45, 25, 4, 88, 96, 18, 101, 7:
*
* 0
* / \
* 1 2
* / \ / \
* 3 4 5 6
* /
* 7
* 101
* 96 45
* 88 25 18 4
* 7
*/
/// <summary>
/// Convert IList to a max-heap from bottom up such that each node maintains the
/// max-heap property (data[Parent[index]] >= data[index] where Parent = index / 2).
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
public static void BuildMaxHeap<T>(IList<T> data) where T : IComparable
{
var heapSize = data.Count;
for (int index = (heapSize / 2) - 1; index > -1; index--)
{
MaxHeapify(data, index, heapSize);
}
}
/* What a min heap looks like from 45, 25, 4, 88, 96, 18, 101, 7:
*
* 0
* / \
* 1 2
* / \ / \
* 3 4 5 6
* /
* 7
*
* 4
* 7 18
* 25 96 45 101
* 88
*/
/// <summary>
/// Convert IList to a min-heap from bottom up such that each node maintains the
/// min-heap property (data[Parent[index]] <= data[index] where Parent = index / 2).
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
public static void BuildMinHeap<T>(IList<T> data) where T : IComparable
{
var heapSize = data.Count;
for (int index = (heapSize / 2) - 1; index > -1; index--)
{
MinHeapify(data, index, heapSize);
}
}
/// <summary>
/// Maintain max-heap property for data at index location for specified heap size
/// such that data[Parent[index]] >= data[index] where Parent = index / 2.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
/// <param name="index"></param>
/// <param name="heapSize"></param>
public static void MaxHeapify<T>(IList<T> data, int index, int heapSize) where T : IComparable
{
var largest = index;
var left = HeapLeft(index);
var right = HeapRight(index);
if (left < heapSize
&& (data[left] != null
&& data[left].CompareTo(data[index]) > 0))
{
largest = left;
}
if (right < heapSize
&& (data[right] != null
&& data[right].CompareTo(data[largest]) > 0))
{
largest = right;
}
if (largest != index)
{
//exchange data[index] with data[largest}
var tempRef = data[index];
data[index] = data[largest];
data[largest] = tempRef;
//recurse
MaxHeapify(data, largest, heapSize);
}
}
/// <summary>
/// Maintain min-heap property for data at index location for specified heap size
/// such that data[Parent[index]] <= data[index]
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
/// <param name="index"></param>
/// <param name="heapSize"></param>
public static void MinHeapify<T>(IList<T> data, int index, int heapSize) where T : IComparable
{
var smallest = index;
var left = HeapLeft(index);
var right = HeapRight(index);
if (left < heapSize
&& (data[left] == null
|| data[left].CompareTo(data[index]) < 0))
{
smallest = left;
}
if (right < heapSize
&& (data[right] == null
|| data[right].CompareTo(data[smallest]) < 0))
{
smallest = right;
}
if (smallest != index)
{
//exchange data[index] with data[largest}
var tempRef = data[index];
data[index] = data[smallest];
data[smallest] = tempRef;
//recurse
MinHeapify(data, smallest, heapSize);
}
}
/// <summary>
/// Extrax max and re-heapify with decremented heapSize.
/// Caller must remember to decrement local heap size.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
/// <param name="heapSize"></param>
/// <returns></returns>
public static T ExtractMax<T>(IList<T> data, int heapSize) where T : IComparable
{
heapSize--;
if (heapSize < 0) throw new IndexOutOfRangeException();
T max = data[0];
data[0] = data[heapSize];
if (heapSize > 0) MaxHeapify(data, 0, heapSize);
return max;
}
/// <summary>
/// Extrax min and re-heapify with decremented heapSize.
/// Caller must remember to decrement local heap size.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
/// <param name="heapSize"></param>
/// <returns></returns>
public static T ExtractMin<T>(IList<T> data, int heapSize) where T : IComparable
{
heapSize--;
if (heapSize < 0) throw new IndexOutOfRangeException();
T max = data[0];
data[0] = data[heapSize];
if (heapSize > 0) MinHeapify(data, 0, heapSize);
return max;
}
public static void MaxIncrease<T>(IList<T> data, int index, T item) where T : IComparable
{
if (null == item || item.CompareTo(data[index]) > 0)
throw new ArgumentException("new item is smaller than the current item", "item");
data[index] = item;
var parent = HeapParent(index);
while (index > 0
&& (data[parent] == null
|| data[parent].CompareTo(data[index]) < 0))
{
//exchange data[index] with data[parent}
var tempRef = data[index];
data[index] = data[parent];
data[parent] = tempRef;
index = parent;
parent = HeapParent(index);
}
}
public static void MinDecrease<T>(IList<T> data, int index, T item) where T : IComparable
{
if (null == item || item.CompareTo(data[index]) < 0)
throw new ArgumentException("new item is greater than the current item", "item");
data[index] = item;
var parent = HeapParent(index);
while (index > 0
&& (data[index] == null
|| data[index].CompareTo(data[parent]) < 0))
{
//exchange data[index] with data[parent}
var tempRef = data[index];
data[index] = data[parent];
data[parent] = tempRef;
index = parent;
parent = HeapParent(index);
}
}
/// <summary>
/// Insert item into max heap. Caller must remember to increment heapSize locally.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
/// <param name="item"></param>
/// <param name="minOfT"></param>
/// <param name="heapSize"></param>
public static void MaxInsert<T>(IList<T> data, T item, T minOfT, int heapSize)
where T : IComparable
{
heapSize++;
if (heapSize < data.Count)
data[heapSize] = minOfT;
else
data.Add(minOfT);
MaxIncrease(data, heapSize - 1, item);
}
/// <summary>
/// Insert item into min heap. Caller must remember to increment heapSize locally.
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="data"></param>
/// <param name="item"></param>
/// <param name="maxOfT"></param>
/// <param name="heapSize"></param>
public static void MinInsert<T>(IList<T> data, T item, T maxOfT, int heapSize)
where T : IComparable
{
heapSize++;
if (heapSize < data.Count)
data[heapSize] = maxOfT;
else
data.Add(maxOfT);
MinDecrease(data, heapSize - 1, item);
}
public static bool MaxContains<T>(IList<T> data, T item, int index, int heapSize)
where T : IComparable
{
if (index >= heapSize) return false;
if (index == 0)
{
if (data[index] == null)
{
if (item == null) return true;
}
else
{
var rootComp = data[index].CompareTo(item);
if (rootComp == 0) return true;
if (rootComp < 0) return false;
}
}
var left = HeapLeft(index);
var leftComp = 0;
if (left < heapSize)
{
if (data[left] == null)
{
if (item == null) return true;
}
else
{
leftComp = data[left].CompareTo(item);
if (leftComp == 0) return true;
}
}
var right = HeapRight(index);
var rightComp = 0;
if (right < heapSize)
{
if (data[right] == null)
{
if (item == null) return true;
}
else
{
rightComp = data[right].CompareTo(item);
if (rightComp == 0) return true;
}
}
if (leftComp < 0 && rightComp < 0) return false;
var leftResult = false;
if (leftComp > 0)
{
leftResult = MaxContains(data, item, left, heapSize);
}
if (leftResult) return true;
var rightResult = false;
if (rightComp > 0)
{
rightResult = MaxContains(data, item, right, heapSize);
}
return rightResult;
}
public static bool MinContains<T>(IList<T> data, T item, int index, int heapSize)
where T : IComparable
{
if (index >= heapSize) return false;
if (index == 0)
{
if (data[index] == null)
{
if (item == null) return true;
}
else
{
var rootComp = data[index].CompareTo(item);
if (rootComp == 0) return true;
if (rootComp > 0) return false;
}
}
var left = HeapLeft(index);
var leftComp = 0;
if (left < heapSize)
{
if (data[left] == null)
{
if (item == null) return true;
}
else
{
leftComp = data[left].CompareTo(item);
if (leftComp == 0) return true;
}
}
var right = HeapRight(index);
var rightComp = 0;
if (right < heapSize)
{
if (data[right] == null)
{
if (item == null) return true;
}
else
{
rightComp = data[right].CompareTo(item);
if (rightComp == 0) return true;
}
}
if (leftComp > 0 && rightComp > 0) return false;
var leftResult = false;
if (leftComp < 0)
{
leftResult = MinContains(data, item, left, heapSize);
}
if (leftResult) return true;
var rightResult = false;
if (rightComp < 0)
{
rightResult = MinContains(data, item, right, heapSize);
}
return rightResult;
}
private static int HeapParent(int i)
{
return i >> 1; // i / 2
}
private static int HeapLeft(int i)
{
return (i << 1) + 1; //i * 2 + 1
}
private static int HeapRight(int i)
{
return (i << 1) + 2; //i * 2 + 2
}
}
If you find any flaws, please do let me know. I will be working on improving this library over time, so look for updates and check GitHub for latest code. Enjoy.