ArrayList.sort() vs PriorityQueue [duplicate]

Question

I need to support a more inserts than reads and keep the data sorted. Which would be better performing:

Using a PriorityQueue providing a comparator

or

Using an ArrayList and calling .sort() after each insert?

Calling .sort() each time feels wrong, but I can't articulate why.

Answer 1

A priority queue will not keep your data sorted. It just allows you to make calls to get its minimum element. If you do that for all the elements in the priority queue, you'll eventually be able to form a list of sorted elements. But then again, you'll have an empty priority queue.

So if you need to be able to read things on the fly on any position without mutating the data-structure, the priority queue is not for you.

What you're probably looking for is to use a TreeSet / TreeMap, that allows you to keep the data sorted and insertions / deletions relatively cheap (roughly O(lg n)).