Repository navigation
IntPriorityQueue for efficient priority queues with integer keys #482
Description
I will be creating a datastructure IntPriorityQueue which is a PriorityQueue which excepts keys from 1:n (n is the input) similar to IntDisjointSets.
This is required to increase the performance in this PR by replacing the index hash table with an array.
Should I PR the code to DataStructures.jl?
Activity
kmsquire commentedon Feb 24, 2019
I think that would be fine. If you post and don't get a response within a day or two, send a gentle bump.🙂
SyxP commentedon Feb 25, 2019
By the way, I think this would only be efficient on dense graphs. I'm not entirely sure whether this would actually be an improvement on sparse graphs.
kmsquire commentedon Feb 25, 2019
If the interface is similar to the existing interface, it's usually nice to have different data structures and algorithms available for comparison for any given problem.
SohamTamba commentedon Mar 2, 2019
@SyxP is right and integer priority queue did not improve performance as much as I thought it would.
See Comment
In case anyone is interested, I have a rough implementation of
int_PriorityQueuewhich can be found here.SyxP commentedon Mar 2, 2019
I feel that this should still be merged in. (Even better, allow the user a control over the type of dictionary used to hash the entries in the PQ, rather than just a Dict as in the current implementation.) This could have uses outside of Dijkstra's algorithm.
oxinabox commentedon Mar 2, 2019
am leaving this open for a bit.
The Int_PQ had noticably less alocations than other methods.
So worth thinking about.
eulerkochy commentedon Mar 6, 2019
Anyone working on this?
SohamTamba commentedon Mar 6, 2019
The allocations are fewer because the
indexarray is allocated statically, instead of a dynamic hash table.Sorry for the late response, didn't see the notification until recently
SohamTamba commentedon Mar 6, 2019
If
Datastructues.jlwants it, I'd be happy to complete it.Instead of keeping two
300line files forPriorityQueueandInt_PriorityQueue, it might be possible to use multiple dispatch to keep one file.The only difference is the hash table is replaced with an array.
nsajko commentedon Oct 9, 2026
possible dup: issue #504
eulerkochy commentedon Oct 9, 2026
I can work on this, have bandwidth now to pursue this till completion