Best way to implement a priority queue

Hi all, I'm looking for a implementation of a priority queue (FIFO) in either javascript or C#. When i was using C++ I used a std::vector together with the pop_heap() and push_heap() functions and now I need a similar solution. Also, since I'm going to use it for A* path-finding I need it to be quite optimized.

Any insights or help would be greatly appreciated!

Thanks
/Henrik

 

The MSDN contains a wealth of information:
http://msdn.microsoft.com/en-us/library/6tc79sx1(VS.80).aspx

In this case, you'll want a Queue: http://msdn.microsoft.com/en-us/library/system.collections.queue.aspx

The Queue I linked will work both for JS and C#. If you use C#, are not making an iPhone game and are comfortable with generics (which I assume you are, considering you mention std::vector) you could also use Queue<T>, which will probably save you a cast or two .

 

Actually I have already looked at using Queue but I'm not sure it has the same functionality as a priority queue?
I might have the concepts a bit mixed up, but reading from Wikipedia the definition states "One can imagine a priority queue as a modified queue, but when one would get the next element off the queue, the highest-priority one is retrieved first." http://en.wikipedia.org/wiki/Priority_queue

So I guess the question is, how do I get a Queue to behave as a "PriorityQueue", or is there a better data type for what I want?

 

sounds like this library might be of interest: http://www.itu.dk/research/c5/

 

Very interesting, I shall look into that =)
One question though, will the C5 lib work on the iPhone?

Thanks

 

No, won't work on the iphone at least for the forseable future.

iPhone is .NET 1.1
In that case I would recommend to invest the 30mins it takes to implement a heap and use that.

 

Yeah that's what I thought, I'll do some searching for existent solutions and see if I can get things working.

Thank you for your help!

 

A heap isn't necessarily the best choice for an A* queue, due to the very specific pattern of adding and removing. You can make a simple, but pretty effective A* queue just by using an array and shuffling items along to accommodate the new items you add. However, arrange it so the head of the queue is at the end of the array (ie, the highest-numbered index) and add new items by searching backwards from the head. If you find you need more performance, you can easily soup this up further. Try pre-sorting all the items you are going to add at a given iteration (insertion sort is better than quicksort in this particular case, but any available sort function will be OK). Then, merge the sorted list with the
queue in the manner of mergesort, again backwards from the head.

 

As Andeee alluded to, they Array class in unity script supports both push and pop operations. You can easily fashion a stack from that.

http://unity3d.com/support/documentation/ScriptReference/Array.html

In terms of performance, perhaps cobbling your own stack together with a linked list is an option.