Answered by:
Creating a priority queue in c#

Hi,
I need to use an efficient PriorityQueue.
The PriorityQueue will be contains a few hundred thousand elements and will be accessed a lot.
Anyone has an idea on how can I simply implement it? (I can't use 'sortedlist' and 'dictionary' because they use a uniqe key)
I'm using .Net 3.5 with VS 2008.
Thanks a lot.
Omri.
Question
Answers

Wikipedia is your friend for learning about the options available to you: http://en.wikipedia.org/wiki/Priority_queue
If you have a limited range of priorities, then as mentioned a bunch of different queues in a sortedlist would be fine. Here's eric lippert's implementation: http://blogs.msdn.com/ericlippert/archive/2007/10/08/pathfindingusingainc30partthree.aspx
If you have a wide range of priorities then you're be more likely looking at some sort of heap based queue. There's probably an implementation on the web somewhere if you try google.
All replies



How do you plan on doing priorities? If its with enum wiht a fix number of fields you can jsut create a seperate Queue for each of these and alwyas check the highest priority queue before moving to the next.
If you want to use an aribratry numeric value you might have issues anyway with people not knowing what value to use or using something too high. It may be best to have a set 3 to 10 levels.

Wikipedia is your friend for learning about the options available to you: http://en.wikipedia.org/wiki/Priority_queue
If you have a limited range of priorities, then as mentioned a bunch of different queues in a sortedlist would be fine. Here's eric lippert's implementation: http://blogs.msdn.com/ericlippert/archive/2007/10/08/pathfindingusingainc30partthree.aspx
If you have a wide range of priorities then you're be more likely looking at some sort of heap based queue. There's probably an implementation on the web somewhere if you try google.

Thanks a lot for all the replies. Greg Beech's links were very usefull
My keys are all string, and I've managed to manipulate them into unique keys now.
I implemented the priority queue using a sorted dictionary (generic).
I only have one problem now:
My keys in the sorted dictionary are sorted in ascending order ( a, b, c, d....).
I want them to be sorted the other way around in a descending order (.... d, c, b, a).
This is important because I need to retrieve/remove from the queue very often and if I access the end of the sorted dictionary it takes a lot of time because it iterates through all the dictionary members until the end of it.
I would appreciate any suggestion. (using a sorted list is also much slower)
Sorry, for the long text
Omri.

A sorted dictionary is a Binary Search Tree, which isn't the most efficient data structure for a priority queue... if thats what your really needing. I'm not sure what constitutes priority in your program (is it the item thats the highest alphabetically?), but if you want efficiency, you need to implement a heap of some sort. A BST will require O(n) time to find a given element in the worst case, where a heap will require O(log n). If your application doesn't need to merge queues often, go with a Binary Heap, as its easy to implement using an array. Plus, if your application needs to peek at the high priority element often, it is a O(1) operation. A little of searching on Google will turn up several example implementations. Good luck,
Jarrod