# Is priority queue more efficient than a vector / list, in terms of inserting an element into a structure which keeps a decreasing / increasing order?

**URL:** <https://discourse.julialang.org/t/is-priority-queue-more-efficient-than-a-vector-list-in-terms-of-inserting-an-element-into-a-structure-which-keeps-a-decreasing-increasing-order/24461>\
**Category:** General Usage\
**Created:** [May 22, 2019, 6:19am UTC](https://discourse.julialang.org/t/is-priority-queue-more-efficient-than-a-vector-list-in-terms-of-inserting-an-element-into-a-structure-which-keeps-a-decreasing-increasing-order/24461 "2019-05-22T06:19:04Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![bsnyh](https://avatars.discourse-cdn.com/v4/letter/b/ce7236/32.png) [@bsnyh](https://discourse.julialang.org/u/bsnyh)\
**Post date:** [May 22, 2019, 6:19am UTC](https://discourse.julialang.org/t/is-priority-queue-more-efficient-than-a-vector-list-in-terms-of-inserting-an-element-into-a-structure-which-keeps-a-decreasing-increasing-order/24461/1 "2019-05-22T06:19:04Z")

</div>

Hi. The task is to insert an element into a structure which keeps a decreasing / increasing order in terms of a certain property, say height, of the elements in the structure. One way to do it, is to use vector / list structure. The operations which are constantly used, are

```julia
pop!(myList) # remove and return the last element from myList

i = something(findlast( e -> e.time >= elementToBeInserted.height, myList ), 0) +1 # compare the element to be inserted to all the elements in list myList one by one to get a vector of values true or false. findlast will return the index of the last true value in this vector. Together with the something function, will return 0 if there is no true values in the created vector. 

insert!(myList, i, elementToBeInserted) # insert the elementToBeInserted to the i-th position of the list myList

```

It looks like a priority queue would be much better. What is your opinion about this then?

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 22, 2019, 6:33am UTC](https://discourse.julialang.org/t/is-priority-queue-more-efficient-than-a-vector-list-in-terms-of-inserting-an-element-into-a-structure-which-keeps-a-decreasing-increasing-order/24461/2 "2019-05-22T06:33:37Z")

</div>

Try

[https://juliacollections.github.io/DataStructures.jl/latest/sorted\_containers.html](https://juliacollections.github.io/DataStructures.jl/latest/sorted_containers.html)

Also, please quote your code.

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [May 22, 2019, 11:02am UTC](https://discourse.julialang.org/t/is-priority-queue-more-efficient-than-a-vector-list-in-terms-of-inserting-an-element-into-a-structure-which-keeps-a-decreasing-increasing-order/24461/3 "2019-05-22T11:02:24Z")

</div>

> [@bsnyh](#):
>
> It looks like a priority queue would be much better. What is your opinion about this then?

Why don’t you try it? There are priority queue and heap data structures in [https://juliacollections.github.io/DataStructures.jl](https://juliacollections.github.io/DataStructures.jl)

---

<div class="post-metadata">

**Author:** ![bsnyh](https://avatars.discourse-cdn.com/v4/letter/b/ce7236/32.png) [@bsnyh](https://discourse.julialang.org/u/bsnyh)\
**Post date:** [May 22, 2019, 11:09am UTC](https://discourse.julialang.org/t/is-priority-queue-more-efficient-than-a-vector-list-in-terms-of-inserting-an-element-into-a-structure-which-keeps-a-decreasing-increasing-order/24461/4 "2019-05-22T11:09:41Z")

</div>

Thank you for the suggestions. I thought someone might have some opinions about it. That’s why I asked earlier.

---

<div class="post-metadata">

**Author:** ![Tamas\_Papp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/tamas_papp/32/25949_2.png) [@Tamas\_Papp](https://discourse.julialang.org/u/Tamas_Papp)\
**Post date:** [May 22, 2019, 11:46am UTC](https://discourse.julialang.org/t/is-priority-queue-more-efficient-than-a-vector-list-in-terms-of-inserting-an-element-into-a-structure-which-keeps-a-decreasing-increasing-order/24461/5 "2019-05-22T11:46:36Z")

</div>

While various algorithms have a reasonably well-established characterization of their (asymptotic) characteristics, speed is up to a constant factor and may depend a lot on the problem details.

This is why it is recommended that you just keep your interfaces flexible and just try out various alternatives. Since we know nothing about your problem, we cannot do this for you. It is always prudent to benchmark bottlenecks, regardless of what theory and experience suggest for choosing a particular algorithm.