Priority Queue in C# with the Help of Heap Data Structure

• Download complete source code

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;
    }
    
    // ... other code
}

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);
    
    // heapify after insert, from end to beginning
    HeapifyFromEndToBeginning(_baseHeap.Count - 1);
}

private int HeapifyFromEndToBeginning(int pos)
{
    if (pos >= _baseHeap.Count) return -1;

    // heap[i] have children heap[2*i + 1] and heap[2*i + 2] and parent heap[(i-1)/ 2];

    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:

1. Exchanging element to be removed with the last element
2. Removing last element, and then
3. 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);
    
    // heapify
    HeapifyFromBeginningToEnd(0);
}

private void HeapifyFromBeginningToEnd(int pos)
{
    if (pos >= _baseHeap.Count) return;
    
    // heap[i] have children heap[2*i + 1] and heap[2*i + 2] and parent heap[(i-1)/ 2];
    
    while (true)
    {
        // on each iteration exchange element with its smallest child
        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)
    {
        // "inverted" comparison
        // direct comparison of integers should return x - y
        return y - x;
    }
}

class Program
{
    static void Main(string[] args)
    {
        // ...
        
        // this priority queue uses "inverted" comparer, 
        // so in fact it is max-priority queue
        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)
    {
        // find element in the collection and remove it
        int elementIdx = _baseHeap.IndexOf(item);
        if (elementIdx < 0) return false;
        
        //remove element
        _baseHeap[elementIdx] = _baseHeap[_baseHeap.Count - 1];
        _baseHeap.RemoveAt(_baseHeap.Count - 1);
        
        // heapify
        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);
    // heapify 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();
    // merge data
    PriorityQueue<TPriority, TValue> result = 
        new PriorityQueue<TPriority, TValue>(pq1.Count + pq2.Count, pq1._comparer);
    result._baseHeap.AddRange(pq1._baseHeap);
    result._baseHeap.AddRange(pq2._baseHeap);
    // heapify data
    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