none
Creating a priority queue in c#

    Question

  •  

    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.

    Monday, March 10, 2008 9:20 PM

Answers

All replies

  • How do you plan on doing priorities.  With just a numeric value?  If so, then a SortedList may be a good bet since it coudl handle all of your queuing for you.  No need to get a thread by uniqueID really, so many not much use for a standard Dictionary.

     

    Monday, March 10, 2008 9:40 PM
  • Check out this post.

    Monday, March 10, 2008 9:40 PM
  • 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.

    Monday, March 10, 2008 9:44 PM
  • 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/path-finding-using-a-in-c-3-0-part-three.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.

     

     

    Monday, March 10, 2008 10:26 PM
  • Thanks a lot for all the replies. Greg Beech's links were very usefull Smile

    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.

    Tuesday, March 11, 2008 2:31 PM
  • 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
    Monday, March 17, 2008 3:18 PM