# Looking for a data structure that

**URL:** <https://discourse.julialang.org/t/looking-for-a-data-structure-that/52365>\
**Category:** New to Julia\
**Created:** [December 25, 2020, 10:47am UTC](https://discourse.julialang.org/t/looking-for-a-data-structure-that/52365 "2020-12-25T10:47:16Z")\
**Posts on this page:** 1\
**Showing post:** 8

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [December 25, 2020, 4:11pm UTC](https://discourse.julialang.org/t/looking-for-a-data-structure-that/52365/8 "2020-12-25T16:11:56Z")

</div>

I will shamelessly offer my package [`TrackingHeaps`](https://github.com/henriquebecker91/TrackingHeaps.jl) as an alternative. However, I am forced to point out it is very similar to the [`DataStructures.MutableBinaryHeap`](https://juliacollections.github.io/DataStructures.jl/latest/heaps/). See [this discussion](https://discourse.julialang.org/t/priority-queue-choice/42783) for the differences. Both structures use vectors inside them and allow support `sizehint!` (however, they just delegate the `sizehint!` to the internal `Vector`s and I think `Base` makes no guarantees about how it works).

I think @lmiq suggestion about linked lists is a little off. Your description of what you want is basically the textbook definition of a heap/‘priority queue’ implemented with a vector/array plus a tracking system to be able to make changes anywhere in the tree. However, the fact that you have thousands of very small heaps may open the possibility of alternative solutions. Such small heaps will live in entirely in the register (or in the L1 cache) if implemented with vectors, so this is a must. Depending on your specifics (if you have memory for allocating the worst-case size of each heap and is losing much time with allocation and loss of locality), then maybe allocating a huge vector (as @lmiq suggested) and treating each 20 elements range as a different heap (using nothing for empty spaces or keeping their sizes in another vector) may be a good solution, but it is very low level and will be hard to work with.

---

_[View the full topic](https://discourse.julialang.org/t/looking-for-a-data-structure-that/52365)._