Какая структура является лучшей для «Получите первые X элементов с лучшим приоритетом»?

Question

У меня много элементов с приоритетом int.Приоритет элемента изменчив.

Количество операций getFirstPriorityElements(int count) - n
Количество операций updatePriorityOfElement(Object o, int priority) - n

Какую структуру наилучшей производительности следует использовать, чтобы получить первые X элементов с наилучшим приоритетом?

Answer 1

A PriorityQueue или TreeSet подойдет вам, если вы хотите иметь постоянный приоритет (очередь - если вы хотите всплыть элементы, набор - если вы хотите сохранить их).

Однако с изменением приоритета вы должны переупорядочивать коллекцию при каждом изменении.Или лучше - перед каждой итерацией.Это должно быть синхронно.

Итак, создайте коллекцию, которая использует пользовательский Comparator, и при каждом вызове iterator() переупорядочивает свои элементы.Например, вы можете расширить TreeSet и переопределить метод iterator().Затем вы звоните next() n раз.