Java - PriorityQueue vs sorted LinkedList

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 operation开发者_运维技巧s.

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.

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)

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.

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).

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.