Enqueue/Dequeue improvement

[ArnaudValensi]

Wouldn't be a good idea to use a HashSet or a Queue by priority?

The complexity of Enqueue/Dequeue would be O(1) instead of O(log n).

[ArnaudValensi]

I think I got it, you need to perform a lot of Contains which is O(n) on a Generic.Queue. Am I right?

[BlueRaja]

How do you create an O(1) priority queue using a hashset and a queue? Neither of those things are sorted by priority.

[ArnaudValensi]

I did this as example: https://gist.github.com/ArnaudValensi/de9a6cdf773c9700d564aac8966ea484

All methods are O(1) but Contains() which is O(n). So it depends on the use case, I know for yours that you need a lot of calls to Contains(), but if you don't, my simple implementation is faster.

I just wanted to understand the choices you made, but I think I got it. Nice work, thanks :)

[BlueRaja]

In your example, Dequeue(), Peek(), and Count are not O(1), they're O(k), where k is the number of possible priority values. That only works if there are a small, discreet number of possible priority values, which is not the case for path-finding.

In general, if you limit the input size to a small number of discreet values, you can often find an improved algorithm. For example, Radix Sort is O(kn), which can be said to be O(n) for (small) constant k.

[ArnaudValensi]

True.

Le samedi 13 août 2016, BlueRaja notifications@github.com a écrit :

In your example, Dequeue(), Peek(), and Count are not O(1), they're O(k), where k is the number of possible priority values. That only works if there are a small, discreet number of possible priority values, which is not the case for path-finding.

— You are receiving this because you modified the open/close state. Reply to this email directly, view it on GitHub https://github.com/BlueRaja/High-Speed-Priority-Queue-for-C-Sharp/issues/12#issuecomment-239635613, or mute the thread https://github.com/notifications/unsubscribe-auth/AAk5RiygpuP8g3CAu0M3PD2fADPI0du4ks5qfhDCgaJpZM4Ji940 .

Arnaud Valensi

Blog: http://geekcoder.org Projet: http://codetown.io http://geekcoder.orgProjet: http://mindup.io http://geekcoder.org

http://geekcoder.org