15,400,390 members
Articles / General Programming / Algorithms
Technical Blog
Posted 11 Nov 2010

121.9K views
25 bookmarked

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

Rate me:
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 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:

C#
```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):

C#
```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);

// 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
C#
```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:

C#
```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:

C#
```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());

// ...
}
} ```

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

C#
```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:

C#
```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);
// heapify data
for (int pos = result._baseHeap.Count / 2 - 1; pos >= 0; pos--)
result.HeapifyFromBeginningToEnd(pos);

return result;
}   ```

## Acknowledgements

Additional thanks to adam.davidson who pointed a bug in the implementation of the `Remove` method.

## Share

 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.

 First Prev Next
 Not exactly priority queue. Egor Elagin29-Sep-14 21:16 Egor Elagin 29-Sep-14 21:16
 Re: Not exactly priority queue. Member 1202398831-Dec-16 19:26 Member 12023988 31-Dec-16 19:26
 My vote of 4 Ali Javani3-Jun-14 21:48 Ali Javani 3-Jun-14 21:48
 How Use It Ali Javani3-Jun-14 21:48 Ali Javani 3-Jun-14 21:48
 Add/Remove Kumait12-Jun-13 19:38 Kumait 12-Jun-13 19:38
 Re: Add/Remove Igor Brejc16-Jul-14 21:15 Igor Brejc 16-Jul-14 21:15
 My vote of 5 Singh Vaibhav16-Mar-13 3:47 Singh Vaibhav 16-Mar-13 3:47
 This has been a great help! Singh Vaibhav16-Mar-13 3:44 Singh Vaibhav 16-Mar-13 3:44
 Thanks Matt Cordell9-Mar-13 11:41 Matt Cordell 9-Mar-13 11:41
 My vote of 3 fereshteh_h19-Jan-13 8:44 fereshteh_h 19-Jan-13 8:44
 issue when enqueueing several elements with the same priority Jeffom17-Jul-12 1:52 Jeffom 17-Jul-12 1:52
 Re: issue when enqueueing several elements with the same priority Patrick Morton17-Jun-13 5:17 Patrick Morton 17-Jun-13 5:17
 No unit tests dgph22-Feb-12 15:15 dgph 22-Feb-12 15:15
 Thoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? LeeJGrissom26-Jan-12 8:00 LeeJGrissom 26-Jan-12 8:00
 Re: Thoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? LeeJGrissom26-Jan-12 8:33 LeeJGrissom 26-Jan-12 8:33
 Re: Thoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? Alexey Kurakin26-Jan-12 9:33 Alexey Kurakin 26-Jan-12 9:33
 Re: Thoughts about a Concurrent:Priority:Queue (aka Lock-free, Thread-safe, PriorityQueue)? Alexey Kurakin26-Jan-12 9:43 Alexey Kurakin 26-Jan-12 9:43
 Why not using SortedSet in .NET 4? shuohus1-Jun-11 19:47 shuohus 1-Jun-11 19:47
 Re: Why not using SortedSet in .NET 4? Alexey Kurakin5-Jun-11 8:38 Alexey Kurakin 5-Jun-11 8:38
 Re: Why not using SortedSet in .NET 4? shuohus5-Jun-11 9:05 shuohus 5-Jun-11 9:05
 Re: Why not using SortedSet in .NET 4? Yoni Erez27-Jan-12 13:46 Yoni Erez 27-Jan-12 13:46
 My vote of 5 Filip D'haene26-May-11 9:32 Filip D'haene 26-May-11 9:32
 wow rexnfx15-Feb-11 4:06 rexnfx 15-Feb-11 4:06