Hi All,
While looking at PriorityQueue implementation in package DataStructures, I realized the algorithm is biased to underlying implementation.
The implementation maintains a Dict and index array as a paired heap array. However, it may help if there can a mechanism through which a user can choose his own underlying data structure or heap than having Julia to force the implementation.
regards,
Sambit
What’s the use case for something like this? The elements in the PQ can be whatever you want; the interal representation is by definition abstracted away: you put your elements in with a given priority, you get them out with the same priority. What would be the benefit of changing the underlying data structure?
I do not have a concrete use case but kind of biased with the C++ STL mindset. Any random access container as a heap can be used in C++ STL.
http://en.cppreference.com/w/cpp/container/priority_queue
For example, Wikipedia explanation for PriorityQueue has multiple implementation possibilities.
The Julia default implementation is “Usual Implementation - Self balancing BST” case. While, that is fine for a library standpoint it may not scale for a Scientific Computing platform requirement as the scientist should be able to change her algorithm at will using the same interface.
@sambitdash, thanks for the comments. I actually want to move toward composable data structures, either in DataStructures.jl, or in a new package. My hope would be to separate basic data structures (e.g., hash tables, heaps, different array/list implementations, etc.) from abstract data types (ADTs–e.g., OrderedDict, PriorityQueue, Stack/Queue, etc.).
Rather than selecting the underlying implementation at run time, I was thinking that different implementations of the abstract data type could be defined using macros which combined the basic data structures. The basic data structures would need to have well-defined interfaces for this to work.
Creating this might get somewhat complicated, and I honestly don’t have the time to work on it much right now, but I hope to formalize these ideas and write them up soon.
Best,
Kevin