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

General Usage
1

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

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?

2

Try

https://juliacollections.github.io/DataStructures.jl/latest/sorted_containers.html

Also, please quote your code.

1 Like
3

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

3 Likes
4

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

5

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.

1 Like