Добавление элемента в автоматически корректируемое место в соответствии с его стоимостью по возрастанию с большей производительностью

Question

У меня был вопрос ранее: Как отсортировать список объектов по двум параметрам для сравнения в Java?

Теперь я хочу сделать это:

I will define a list and when I add en element it it will find the correct place for it according the its cost. (I don't want to generate a list that has unordered elements and sort them after that)

Я хочу сделать это с максимальной производительностью.Я имею в виду, что мой список будет упорядочен каждый раз, поэтому, когда я хочу добавить элемент в этот список, это будет добавление в упорядоченный список.Стоимость упорядоченного списка может быть O (logn) при поиске правильного места с помощью бинарного поиска (даже при поиске места, возможно, с меньшими затратами, добавление элемента в этот список (например, ArrayList) может потребовать больше затрат, чем его преимуществ, поэтому вы можете предложить добавитьэлемент без реализации двоичного поиска, если вы считаете, что использование этого класса (ArrayList и т. д. и т. д.) не подходит для total )

Answer 1

Вы можете использовать TreeSet (который O (log n) вставляет и O (1) удаляет первым) или PriorityQueue (который O (1) вставляет и O (log n) удаляет первым)

Примечание: TreeSet сортируется при вставке, PriorityQueue - нет.

Единственный способ избежать операции O (log n) состоит в том, чтобы сделать некоторые строгие предположения о диапазоне возможных значений, которые вряд ли будут здесь полезны.