Click here to Skip to main content
Click here to Skip to main content
Technical Blog

Priority queue in C# with the help of heap data structure

, 29 May 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
This article describes generic priority queue implementation in C#, which uses min-heap as underlying storage.

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 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 following:

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Alexey Kurakin

Russian Federation Russian Federation
My name is Alexey.
 
I am PhD student at MIPT in the area of Computer Vision. In 2009, I am obtained MS degree in the area of Data Mining and Machine Learning. Besides my scientific interests, I am fond of creating complicated software and solve difficult technical problems.
 
I am experienced C# developed. Also I have skills in Matlab, C++, Assembler and some other programming languages.

Comments and Discussions

 
GeneralNot exactly priority queue. PinmemberEgor Elagin29-Sep-14 22:16 
GeneralMy vote of 4 PinmemberAli Javani3-Jun-14 22:48 
QuestionHow Use It PinmemberAli Javani3-Jun-14 22:48 
QuestionAdd/Remove PinmemberMember 849014912-Jun-13 20:38 
AnswerRe: Add/Remove PinmemberIgor Brejc16-Jul-14 22:15 
GeneralMy vote of 5 PinmemberSingh Vaibhav16-Mar-13 4:47 
GeneralThis has been a great help! PinmemberSingh Vaibhav16-Mar-13 4:44 
QuestionThanks PinmemberMatt Cordell9-Mar-13 12:41 
GeneralMy vote of 3 Pinmemberfereshteh_h19-Jan-13 9:44 
Bugissue when enqueueing several elements with the same priority [modified] PinmemberJeffom17-Jul-12 2:52 
GeneralRe: issue when enqueueing several elements with the same priority PinmemberPatrick Morton17-Jun-13 6:17 
QuestionNo unit tests Pinmemberdgph22-Feb-12 16:15 
QuestionThoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? PinmemberMember 435925926-Jan-12 9:00 
AnswerRe: Thoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? [modified] PinmemberMember 435925926-Jan-12 9:33 
GeneralRe: Thoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? PinmemberAlexey Kurakin26-Jan-12 10:33 
AnswerRe: Thoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? PinmemberAlexey Kurakin26-Jan-12 10:43 
GeneralWhy not using SortedSet<T> in .NET 4? Pinmembershuohus1-Jun-11 20:47 
GeneralRe: Why not using SortedSet in .NET 4? PinmemberAlexey Kurakin5-Jun-11 9:38 
GeneralRe: Why not using SortedSet in .NET 4? Pinmembershuohus5-Jun-11 10:05 
GeneralRe: Why not using SortedSet in .NET 4? PinmemberYoni Erez27-Jan-12 14:46 
GeneralMy vote of 5 PinmemberFilip D'haene26-May-11 10:32 
Generalwow Pinmemberrexnfx15-Feb-11 5:06 
GeneralMy vote of 5 Pinmemberadam.davidson17-Nov-10 7:25 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web01 | 2.8.1411023.1 | Last Updated 29 May 2011
Article Copyright 2010 by Alexey Kurakin
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid