# Implementing a sychronized priority queue in c#

**Posted:**17/09/2014 |

**Author:**netmatze |

**Filed under:**.net, Algorithm, c#, concurrency, Data Structures |

**Tags:**c#, data structure, list, priority queue, synchronized | Leave a comment

At my last project i used a queue to add download and upload tasks of documents. After most of the implementation was done i discovered that some of the upload and download tasks should have higher priority than others. So for my implementation i used a synchnoized wrapper of the .net queue. And with a queue it is not possible to work with items that have different priorities. At the following picture the use of a queue is ilustrated.

So at that point i was looking for a priority queue. The problem is that the .net framework does not provide such a data structure, so i had to implement it myself. The following picture shows how a priority queue works.

So if you want to implement a priority queue you need an underlying data structure. That data structure has to reorganize the enqued items so that the item with the highest priority is dequeued first. So one possible data structure is a list you reorder. If a item with a higher priority is enqued you bring it to the front of the list. That works fine with hundred of added items. But if you have several thousend items to enqueue the solution with the list gets slower and slower. Then you need a priority queue that is implemented with a tree structure. You could use a balanced search tree like an AVL tree, but most of data structure books recomend a binary heap. So i decided to implement my priority queue with two modes. In one mode it internaly uses a list, in the second mode it uses a binary heap. If you want to look at the code or use the priority queue, i added it to codeplex. (http://priorityQueue.codeplex.com).

Here is the uml class diagram and a two tests that show the use of the priority queue in linked list and in binary heap mode.

[TestClass] public class PriorityQueueTests { [TestMethod] public void PriorityQueueListModeTest() { PriorityQueue<int, string> priorityQueue = new PriorityQueue<int, string>(PriorityQueueMode.LinkedList); priorityQueue.Enqueue(1, "A"); priorityQueue.Enqueue(2, "B"); priorityQueue.Enqueue(3, "C"); priorityQueue.Enqueue(4, "D"); priorityQueue.Enqueue(5, "E"); priorityQueue.Enqueue(6, "F"); var count = priorityQueue.Count; var result = priorityQueue.Dequeue(); Assert.AreEqual(result, "F"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "E"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "D"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "C"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "B"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "A"); } [TestMethod] public void PriorityQueueBinaryHeapModeTest() { PriorityQueue<int, string> priorityQueue = new PriorityQueue<int, string>(PriorityQueueMode.BinaryHeap); priorityQueue.Enqueue(1, "A"); priorityQueue.Enqueue(2, "B"); priorityQueue.Enqueue(3, "C"); priorityQueue.Enqueue(4, "D"); priorityQueue.Enqueue(5, "E"); priorityQueue.Enqueue(6, "F"); var count = priorityQueue.Count; var result = priorityQueue.Dequeue(); Assert.AreEqual(result, "F"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "E"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "D"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "C"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "B"); result = priorityQueue.Dequeue(); Assert.AreEqual(result, "A"); } }

The two tests show that the items with higher priority are ranked at the top of the priority queue and the items with lower priority are ranked at the end of the priority queue.