# PriorityQueue and containers

**URL:** <https://discourse.julialang.org/t/priorityqueue-and-containers/4796>\
**Category:** Data\
**Created:** [July 12, 2017, 8:34am UTC](https://discourse.julialang.org/t/priorityqueue-and-containers/4796 "2017-07-12T08:34:49Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![sambitdash](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sambitdash/32/1377_2.png) [@sambitdash](https://discourse.julialang.org/u/sambitdash)\
**Post date:** [July 12, 2017, 8:34am UTC](https://discourse.julialang.org/t/priorityqueue-and-containers/4796/1 "2017-07-12T08:34:49Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![anon94023334](https://avatars.discourse-cdn.com/v4/letter/a/e274bd/32.png) [@anon94023334](https://discourse.julialang.org/u/anon94023334)\
**Post date:** [July 12, 2017, 2:20pm UTC](https://discourse.julialang.org/t/priorityqueue-and-containers/4796/2 "2017-07-12T14:20:52Z")

</div>

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?

---

<div class="post-metadata">

**Author:** ![sambitdash](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/sambitdash/32/1377_2.png) [@sambitdash](https://discourse.julialang.org/u/sambitdash)\
**Post date:** [July 12, 2017, 2:50pm UTC](https://discourse.julialang.org/t/priorityqueue-and-containers/4796/3 "2017-07-12T14:50:43Z")

</div>

@anon94023334

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](http://en.cppreference.com/w/cpp/container/priority_queue)

For example, Wikipedia explanation for PriorityQueue has multiple implementation possibilities.

> **[Priority queue](https://en.wikipedia.org/wiki/Priority_queue)**
>
> In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure. Each element in a priority queue has an associated priority. In a priority queue, elements with high priority are served before elements with low priority. In some implementations, if two elements have the same priority, they are served in the same order in which they were enqueued. In other implementations, the order of elements with the same priority is undefined.
> While priority...

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.

---

<div class="post-metadata">

**Author:** ![kevin.squire](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kevin.squire/32/62_2.png) [@kevin.squire](https://discourse.julialang.org/u/kevin.squire)\
**Post date:** [July 12, 2017, 5:18pm UTC](https://discourse.julialang.org/t/priorityqueue-and-containers/4796/4 "2017-07-12T17:18:06Z")

</div>

@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