Which implementation is less "heavy": PriorityQueue or a sorted LinkedList (using a Comparator)?
I want to have all the items sorted. The insertion will be very frequent and ocasionally I will have to run all the list to make some operations.
Join Stack Overflow to learn, share knowledge, and build your career.
Which implementation is less "heavy": PriorityQueue or a sorted LinkedList (using a Comparator)?
I want to have all the items sorted. The insertion will be very frequent and ocasionally I will have to run all the list to make some operations.
A LinkedList
is the worst choice. Either use an ArrayList
(or, more generally, a RandomAccess
implementor), or PriorityQueue
. If you do use a list, sort it only before iterating over its contents, not after every insert.
One thing to note is that the PriorityQueue
iterator does not provide the elements in order; you'll actually have to remove the elements (empty the queue) to iterate over its elements in order.
List
. Since the user was specifically asking whether to use a List
or a PriorityQueue
, it wouldn't make sense to use a queue with its extra overhead if you end up using a list every time anyway.
– erickson
Aug 21 '14 at 15:16
You should implement both and then do performance testing on actual data to see which works best in your specific circumstances.
I have made a small benchmark on this issue. If you want your list to be sorted after the end of all insertions then there is almost no difference between PriorityQueue
and LinkedList
(LinkedList is a bit better, from 5 to 10 percents quicker on my machine), however if you use ArrayList you will get almost 2 times quicker sorting than in PriorityQueue.
In my benchmark for lists I measured time from the beginning of filling it with values till the end of sorting. For PriorityQueue - from the beginning of filling till the end of polling all elements(because elements get ordered in PriorityQueue while removing them as mentioned in erickson answer)
If you use a LinkedList
, you would need to resort the items each time you added one and since inserts are frequent, I wouldn't use a LinkedList
. So in this case, I would use a PriorityQueue
's If you will only be adding unique elements to the list, I recommend using a SortedSet
(one implementation is the TreeSet
).
java.util.LinkedList
is optimized for adding elements to the end of the list, making it an O(1) operation. However, sorting a LinkedList
has horrible performance.
– erickson
May 20 '10 at 22:19
java.util.ArrayDeque
.
– Alexander Pogrebnyak
May 20 '10 at 22:37
SortedSet
! It is the set's Ordering
that determines whether or not a value is already in the set, not equals()
. For example, if you have a SortedSet
of Vector
s ordered on the size of the vector, then the set will only hold one vector of length 4. Only use SortedSet
if you are sure that different values will never be considered equal by the set's Ordering#compare
.
– AmigoNico
Dec 22 '13 at 10:11
adding objects to the priority queue will be O log(n) and the same for each pol. If you are doing inserts frequently on very large queues then this could impact performance. Inserting into the top of an ArrayList is constant so on the whole all those inserts will go faster on the ArrayList than on the priority queue.
If you need to grab ALL the elements in sorted order the Collections.sort will work in about O n log (n) time total. Where as each pol from the priority queue will be O log(n) time, so if you grab all n things from the queue that will again be O n log (n).
The use case where priority queue wins is if you are trying to find what the biggest value in the queue is at any given time. To do that with the ArrayList you have to sort the whole list each time you want to know the biggest. But with the priority queue it always knows what the biggest value is.
There is a fundamental difference between the two data structures and they are not as easily interchangeable as you might think.
According to the PriorityQueue documentation:
The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order.
Use an ArrayList and call Collections.sort() on it only before iterating the list.
The issue with PriorityQueue
is that you have to empty the queue to get the elements in order. If that is what you want then it is a fine choice. Otherwise you could use an ArrayList
that you sort only when you need the sorted result or, if the items are distinct (relative to the comparator), a TreeSet
. Both TreeSet
and ArrayList
are not very 'heavy' in terms of space; which is faster depends on the use case.
Do you need it sorted at all times? If that's the case, you might want to go with something like a tree-set (or other SortedSet with a fast lookup).
If you only need it sorted occasionally, go with a linked list and sort it when you need access. Let it be unsorted when you don't need access.
java.util.PriorityQueue
is
"An unbounded priority queue based on a priority heap"
. The heap data structure make much more sense than a linked list
I can see two options, which one is better depends on whether you need to be able to have duplicate items.
If you don't need to maintain duplicate items in your list, I would use a SortedSet (probably a TreeSet).
If you need maintain duplicate items, I would go with an LinkedList and insert new items into the list in the correct order.
The PriorityQueue doesn't really fit unless you want to remove the items whenever you do operations.
Going along with the others, make sure you use profiling to make sure you're picking out the correct solution for your particular problem.
IMHO: we don't need PriorityQueue if if have LinkedList. I can sort queue with LinkedList faster than with PriorityQueue. e.g.
Queue list = new PriorityQueue();
list.add("1");
list.add("3");
list.add("2");
while(list.size() > 0) {
String s = list.poll().toString();
System.out.println(s);
}
I believe this code works too long, cause each time I add element it will sort elements. but if I will use next code:
Queue list = new LinkedList();
list.add("1");
list.add("3");
list.add("2");
List lst = (List)list;
Collections.sort(lst);
while(list.size() > 0) {
String s = list.poll().toString();
System.out.println(s);
}
I think this code will sort only once and it will be faster that using PriorityQueue. So, I can once sort my LinkedList once, before using it, in any case and it will work faster. And even if it sort the same time I don't really need PriorityQueue, we really don't need this class.