Recently, I needed a priority queue data structure in one of my C# programs. If you do not know, priority queue is a collection, which stores objects along with their priorities and supports the following operations:
- Insert element with its priority
- Get element with minimum priority and remove it from the collection
- Get element with minimum priority without removing it from the collection
Unfortunately, C# class library does not have such collection, so I started to search out-of-the-box solutions in the internet. I had found several articles on the topic (for example this and this), but these articles describe non-generic solutions, but I needed a generic one. So I had a choice: improve one of the existing solutions to be generic or write my own. Due to the fact that implementation of priority queue would not take much efforts, I decided to write my own.
Below the source code and some implementation details are presented. For the most impatient, code could be downloaded here.
Implementation Details
There are a variety of ways in which priority queue can be implemented. A very simple and naive implementation is to use sorted or unsorted list, but this is not efficient. More efficient implementations are based on heap data structure. Heap is a tree-based data structure with the min-heap or max-heap property. Min-heap property means that key of every child node should be greater or equal to the key of parent node. Max-heap property means that the key of every child node should be less or equal to the key of parent node.
In my implementation, I used min-binary heap. Binary heap can be efficiently stored in the array, despite the fact that heap is a tree-based structure. If we use zero-based array arr
to store binary heap data, then node at arr[i]
will have children nodes arr[2*i + 1]
and arr[2*i + 2]
, and parent node arr[(i-1)/2]
.
Algorithmic details about binary heaps could be found in the Wikipedia article, and in many books about algorithm, for example in this one.
I store the heap data in the C# List
collection. In addition, to customize comparison operations, I use IComparer<TPriority>
for comparison of priorities.
The code of the PriorityQueue<TPriority, TValue>
fields and constructor is as follows:
public class PriorityQueue<TPriority, TValue>
{
private List<KeyValuePair<TPriority, TValue>> _baseHeap;
private IComparer<TPriority> _comparer;
public PriorityQueue()
: this(Comparer<TPriority>.Default)
{
}
public PriorityQueue(IComparer<TPriority> comparer)
{
if (comparer == null)
throw new ArgumentNullException();
_baseHeap = new List<KeyValuePair<TPriority, TValue>>();
_comparer = comparer;
}
}
Insertions into binary heap are performed by adding the element to the end of the underlying list, and "heapifying" it (to maintain heap property):
public void Enqueue(TPriority priority, TValue value)
{
Insert(priority, value);
}
private void Insert(TPriority priority, TValue value)
{
KeyValuePair<TPriority, TValue> val =
new KeyValuePair<TPriority, TValue>(priority, value);
_baseHeap.Add(val);
HeapifyFromEndToBeginning(_baseHeap.Count - 1);
}
private int HeapifyFromEndToBeginning(int pos)
{
if (pos >= _baseHeap.Count) return -1;
while (pos > 0)
{
int parentPos = (pos - 1) / 2;
if (_comparer.Compare(_baseHeap[parentPos].Key, _baseHeap[pos].Key) > 0)
{
ExchangeElements(parentPos, pos);
pos = parentPos;
}
else break;
}
return pos;
}
private void ExchangeElements(int pos1, int pos2)
{
KeyValuePair<TPriority, TValue> val = _baseHeap[pos1];
_baseHeap[pos1] = _baseHeap[pos2];
_baseHeap[pos2] = val;
}
Element removals are somewhat similar to insertions, because we do it by:
- Exchanging element to be removed with the last element
- Removing last element, and then
- Heapifying
public TValue DequeueValue()
{
return Dequeue().Value;
}
public KeyValuePair<TPriority, TValue> Dequeue()
{
if (!IsEmpty)
{
KeyValuePair<TPriority, TValue> result = _baseHeap[0];
DeleteRoot();
return result;
}
else
throw new InvalidOperationException("Priority queue is empty");
}
private void DeleteRoot()
{
if (_baseHeap.Count <= 1)
{
_baseHeap.Clear();
return;
}
_baseHeap[0] = _baseHeap[_baseHeap.Count - 1];
_baseHeap.RemoveAt(_baseHeap.Count - 1);
HeapifyFromBeginningToEnd(0);
}
private void HeapifyFromBeginningToEnd(int pos)
{
if (pos >= _baseHeap.Count) return;
while (true)
{
int smallest = pos;
int left = 2 * pos + 1;
int right = 2 * pos + 2;
if (left < _baseHeap.Count &&
_comparer.Compare(_baseHeap[smallest].Key, _baseHeap[left].Key) > 0)
smallest = left;
if (right < _baseHeap.Count &&
_comparer.Compare(_baseHeap[smallest].Key, _baseHeap[right].Key) > 0)
smallest = right;
if (smallest != pos)
{
ExchangeElements(smallest, pos);
pos = smallest;
}
else break;
}
}
And here are the operations to get element with minimum priority without removing it, and to check whether priority queue is empty:
public KeyValuePair<TPriority, TValue> Peek()
{
if (!IsEmpty)
return _baseHeap[0];
else
throw new InvalidOperationException("Priority queue is empty");
}
public TValue PeekValue()
{
return Peek().Value;
}
public bool IsEmpty
{
get { return _baseHeap.Count == 0; }
}
So if you combine all the above mentioned code in one class, you'll get ready to use priority queue.
If you need max-priority queue (i.e., priority queue which extracts elements with maximum priorities first), you may invert comparison operations in the above mentioned code or use custom comparer. The following example demonstrates usage of custom comparer:
class MyComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return y - x;
}
}
class Program
{
static void Main(string[] args)
{
PriorityQueue<int, string> q = new PriorityQueue<int, string>
(data, new MyComparer());
}
}
Some Additional Code
In addition to the above mentioned functionality, you may want your priority queue to implement ICollection<>
interface (for example to write LINQ queries), or make methods to merge queues and create queues from given array in O(n) time.
Implementation of ICollection<>
is trivial, especially if you are satisfied with the fact that the GetEnumerator
method returns enumerator which does not iterate through collection in ascending/descending order of priorities. I did not implement ordered enumerator, so below only the Remove
method is written (it requires heapifying data after removal):
public class PriorityQueue<TPriority, TValue> :
ICollection<KeyValuePair<TPriority, TValue>>
{
#region ICollection<KeyValuePair<TPriority, TValue>> implementation
public bool Remove(KeyValuePair<TPriority, TValue> item)
{
int elementIdx = _baseHeap.IndexOf(item);
if (elementIdx < 0) return false;
_baseHeap[elementIdx] = _baseHeap[_baseHeap.Count - 1];
_baseHeap.RemoveAt(_baseHeap.Count - 1);
int newPos = HeapifyFromEndToBeginning(elementIdx);
if (newPos == elementIdx)
HeapifyFromBeginningToEnd(elementIdx);
return true;
}
#endregion
Creation from the array and merging (both in O(n) time) are implemented in the following way:
public PriorityQueue(IEnumerable<KeyValuePair<TPriority, TValue>> data,
IComparer<TPriority> comparer)
{
if (data == null || comparer == null)
throw new ArgumentNullException();
_comparer = comparer;
_baseHeap = new List<KeyValuePair<TPriority, TValue>>(data);
for (int pos = _baseHeap.Count / 2 - 1; pos >= 0; pos--)
HeapifyFromBeginningToEnd(pos);
}
public static PriorityQueue<TPriority, TValue> MergeQueues
(PriorityQueue<TPriority, TValue> pq1,
PriorityQueue<TPriority, TValue> pq2,
IComparer<TPriority> comparer)
{
if (pq1 == null || pq2 == null || comparer == null)
throw new ArgumentNullException();
PriorityQueue<TPriority, TValue> result =
new PriorityQueue<TPriority, TValue>(pq1.Count + pq2.Count, pq1._comparer);
result._baseHeap.AddRange(pq1._baseHeap);
result._baseHeap.AddRange(pq2._baseHeap);
for (int pos = result._baseHeap.Count / 2 - 1; pos >= 0; pos--)
result.HeapifyFromBeginningToEnd(pos);
return result;
}
Once again, the complete code could be downloaded here.
Acknowledgements
Additional thanks to adam.davidson who pointed a bug in the implementation of the Remove
method.
CodeProject