PriorityQueue and containers


#1

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


#2

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?


#3

@sbromberger

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.


#4

@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