У меня очередь приоритетов в Java целых чисел:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
Когда я звоню, pq.poll()
я получаю минимальный элемент.
Вопрос: как изменить код, чтобы получить максимальный элемент?
java
collections
priority-queue
Борут Флис
источник
источник
Ответы:
Как насчет этого:
Collections.reverseOrder()
Обеспечивает ,Comparator
что бы отсортировать элементы вPriorityQueue
в виде на противоположном порядке в их естественном порядке в этом случае.источник
Collections.reverseOrder()
также перегружен для использования компаратора, поэтому он также работает, если вы сравниваете пользовательские объекты.PriorityQueue(Comparator<? super E> comparator)
.Вы можете использовать лямбда-выражение, начиная с Java 8.
Следующий код напечатает 10, больше.
Лямбда-функция принимает два целых числа в качестве входных параметров, вычитает их друг из друга и возвращает арифметический результат. Лямбда-функция реализует функциональный интерфейс
Comparator<T>
. (Это используется вместо анонимного класса или дискретной реализации.)источник
(x, y) -> y - x
может не подходить для длинных целых чисел из-за переполнения. Например, числа y = Integer.MIN_VALUE и x = 5 дают положительное число. Лучше использоватьnew PriorityQueue<>((x, y) -> Integer.compare(y, x))
. Хотя, @Edwin Dalorzo предлагает лучшее решениеCollections.reverseOrder()
.Вы можете предоставить настраиваемый
Comparator
объект, который ранжирует элементы в обратном порядке:Теперь очередь с приоритетом изменит все свои сравнения, поэтому вы получите максимальный элемент, а не минимальный элемент.
Надеюсь это поможет!
источник
if (rhs < lhs) return +1;
if (rhs > lhs) return -1;
if (lhs < rhs) return +1; if (lhs > rhs) return -1;
источник
b-a
может вызвать,overflow
поэтому следует избегать его использования и использоватьCollections.reverseOrder();
в качестве компаратора или заменить ba, наInteger.compare(a,b);
которое было добавленоJava 8
В Java 8+ вы можете создать очередь с максимальным приоритетом одним из следующих методов:
Способ 1:
Способ 2:
Способ 3:
источник
Элементы приоритетной очереди упорядочиваются в соответствии с их естественным порядком или с помощью компаратора, предоставленного во время создания очереди.
Компаратор должен переопределить метод сравнения.
Метод сравнения по умолчанию возвращает отрицательное целое число, ноль или положительное целое число, поскольку первый аргумент меньше, равен или больше второго.
По умолчанию PriorityQueue, предоставляемый Java, - это Min-Heap, если вы хотите, чтобы максимальная куча была следующей, это код
Ссылка: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator ()
источник
Вот пример Max-Heap на Java:
На выходе будет 10
источник
Это может быть достигнуто с помощью приведенного ниже кода в Java 8, который представил конструктор, который принимает только компаратор.
источник
Вы можете использовать
MinMaxPriorityQueue
(это часть библиотеки Guava): вот документация . Вместо этогоpoll()
вам нужно вызватьpollLast()
метод.источник
Измените PriorityQueue на MAX PriorityQueue Метод 1: очередь pq = new PriorityQueue <> (Collections.reverseOrder ()); Метод 2: очередь pq1 = new PriorityQueue <> ((a, b) -> b - a); Давайте посмотрим на несколько примеров:
Возьмем известную проблему интервью: K-й самый большой элемент в массиве с использованием PriorityQueue
По-другому :
Как мы видим, оба дают одинаковый результат.
источник
Этого можно добиться, используя
источник
Я только что провел симуляцию Монте-Карло на обоих компараторах с двойной сортировкой кучи min max, и они оба пришли к одному и тому же результату:
Это максимальные компараторы, которые я использовал:
(A) Сборки встроенного компаратора
(B) Пользовательский компаратор
источник
if (rhs < lhs) return +1;
if (rhs> lhs) return -1;Вы можете попробовать что-то вроде:
Что работает для любой другой базовой функции сравнения, которая у вас может быть.
источник
источник
Вы можете попробовать толкать элементы с обратным знаком. Например: добавить a = 2 & b = 5, а затем опрос b = 5.
После опроса главы очереди измените знак для вашего использования. Это напечатает 5 (более крупный элемент). Может использоваться в наивных реализациях. Определенно ненадежное решение. Не рекомендую.
источник
Мы можем сделать это, создав наш класс CustomComparator , реализующий интерфейс Comparator, и переопределив его метод сравнения. Ниже приведен код того же:
источник