Самый быстрый способ изменить порядок PriorityQueue в Java

Question

В моей реализации я добавляю объекты в PriorityQueue на основе значения параметра a, который у них есть. Проще говоря, я добавляю элементы в PriorityQueue так, чтобы элементы с наибольшим значением находились перед очередью, используя Comparator.comparingDouble(Object -> -Object.a). Всякий раз, когда размер очереди превышает предопределенный порог, я опрашиваю элемент для очереди. Таким образом, очередь будет содержать элементы с наиболее отрицательным значением.

В следующей части моего кода я хочу рассмотреть элементы в очереди в порядке возрастания значения a, таким образом, обратная очередь к моей очереди в настоящее время.

Какой самый быстрый способ сделать это / какие другие варианты первой части у меня есть?

Далее я разработал небольшой пример, чтобы проиллюстрировать, что я хочу получить. Предположим, у меня есть список из пяти элементов [4,2,7,9,1], и я хочу оставить три самых маленьких. Тогда приоритет будет равен:

• [4]
• [4,2]
• [7,4,2]
• [9 , 7,4,2] -> [7,4,2] после опроса ()
• [7,4,2,1] -> [4,2,1] после опроса ()

Для моей следующей части кода я бы хотел перебрать обратную сторону этой очереди: [1,2,4].

Обратите внимание, что этот пример довольно прост и прост, но в моем коде список может содержать более 1 000 000 элементов.

Я открыт для всех предложений!

Answer 1

PriorityQueue реализован как структура данных кучи; как таковые, его элементы на самом деле не упорядочены. Найти самый большой элемент в куче - O(1), а найти самый маленький - O(n). Вы не сможете легко получить обратное представление из самой структуры данных.

Таким образом, ответ на ваш вопрос будет дорогостоящим в вычислительном отношении:

PriorityQueue<Integer> queue;
// this step will be expensive ~ n log(n)
List<Integer> values = queue.stream().sorted().collect(Collectors.toList());
// this also won't be cheap ~ n
Collections.reverse(values);

В зависимости от ваших моделей использования Возможно, вы захотите выбрать структуру данных, которая может быть более дорогой для добавления и удаления, но дешевле изменить. TreeSet приходит на ум с его .iterator() и .descendingIterator() методами.