У меня очередь приоритетов в Java целых чисел:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
Когда я вызываю pq.poll()
, я получаю минимальный элемент.
Вопрос: как изменить код, чтобы получить максимальный элемент?
У меня очередь приоритетов в Java целых чисел:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
Когда я вызываю pq.poll()
, я получаю минимальный элемент.
Вопрос: как изменить код, чтобы получить максимальный элемент?
Как насчет этого:
PriorityQueue<Integer> queue = new PriorityQueue<>(10, Collections.reverseOrder());
queue.offer(1);
queue.offer(2);
queue.offer(3);
//...
Integer val = null;
while( (val = queue.poll()) != null) {
System.out.println(val);
}
Collections.reverseOrder()
предоставляет Comparator
, который в этом случае сортирует элементы в PriorityQueue
в обратном порядке к их естественному порядку.
Collections.reverseOrder()
также перегружен для использования компаратора, поэтому он также работает, если вы сравниваете пользовательские объекты.
- person flying sheep; 04.07.2013
PriorityQueue(Comparator<? super E> comparator)
.
- person abhisheknirmal; 12.05.2016
Вы можете использовать лямбда-выражение, начиная с Java 8.
Следующий код напечатает 10, больше.
// There is overflow problem when using simple lambda as comparator, as pointed out by Фима Гирин.
// PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
PriorityQueue<Integer> pq =new PriorityQueue<>((x, y) -> Integer.compare(y, x));
pq.add(10);
pq.add(5);
System.out.println(pq.peek());
Лямбда-функция принимает два целых числа в качестве входных параметров, вычитает их друг из друга и возвращает арифметический результат. Лямбда-функция реализует функциональный интерфейс Comparator<T>
. (Это используется вместо анонимного класса или дискретной реализации.)
(x, y) -> y - x
, может не подходить для длинных целых чисел из-за переполнения. Например, числа y = Integer.MIN_VALUE и x = 5 дают положительное число. Лучше использовать new PriorityQueue<>((x, y) -> Integer.compare(y, x))
. Хотя @Edwin Dalorzo дает лучшее решение использовать Collections.reverseOrder()
.
- person Фима Гирин; 21.01.2018
В Java 8+ вы можете создать очередь с максимальным приоритетом одним из следующих методов:
Способ 1:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
Способ 2:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a);
Способ 3:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a));
Вы можете предоставить собственный объект Comparator
, который ранжирует элементы в обратном порядке:
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() {
public int compare(Integer lhs, Integer rhs) {
if (lhs < rhs) return +1;
if (lhs.equals(rhs)) return 0;
return -1;
}
});
Теперь очередь с приоритетом изменит все свои сравнения, так что вы получите максимальный элемент, а не минимальный элемент.
Надеюсь это поможет!
if (rhs < lhs) return +1;
if (rhs > lhs) return -1;
- person Tia; 10.02.2016
if (lhs < rhs) return +1; if (lhs > rhs) return -1;
- person Tia; 23.02.2016
public int compare(Integer lhs, Integer rhs)
, чтобы избавиться от сообщения об ошибке "cannot implement compare(T,T) in Comparator"
- person Shrikant Prabhu; 29.05.2018
return rhs - lhs
должно подойти.
- person CharlesC; 07.04.2020
Элементы приоритетной очереди упорядочиваются в соответствии с их естественным порядком или компаратором, предоставленным во время построения очереди.
Компаратор должен переопределить метод сравнения.
int compare(T o1, T o2)
Метод сравнения по умолчанию возвращает отрицательное целое число, ноль или положительное целое число, поскольку первый аргумент меньше, равен или больше второго.
По умолчанию PriorityQueue, предоставляемый Java, - это Min-Heap, если вы хотите, чтобы максимальная куча была следующей, это код
public class Sample {
public static void main(String[] args) {
PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer lhs, Integer rhs) {
if(lhs<rhs) return +1;
if(lhs>rhs) return -1;
return 0;
}
});
q.add(13);
q.add(4);q.add(14);q.add(-4);q.add(1);
while (!q.isEmpty()) {
System.out.println(q.poll());
}
}
}
Ссылка: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator().
Вот пример Max-Heap на Java:
PriorityQueue<Integer> pq1= new PriorityQueue<Integer>(10, new Comparator<Integer>() {
public int compare(Integer x, Integer y) {
if (x < y) return 1;
if (x > y) return -1;
return 0;
}
});
pq1.add(5);
pq1.add(10);
pq1.add(-1);
System.out.println("Peek: "+pq1.peek());
На выходе будет 10
Это может быть достигнуто с помощью приведенного ниже кода в Java 8, который представил конструктор, который принимает только компаратор.
PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
Этого можно добиться, используя
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
Мы можем сделать это, создав наш класс CustomComparator, реализующий интерфейс Comparator, и переопределив его метод сравнения. Ниже приведен код того же:
import java.util.PriorityQueue;
import java.util.Comparator;
public class Main
{
public static void main(String[] args) {
PriorityQueue<Integer> nums = new PriorityQueue<>(new CustomComparator());
nums.offer(21);
nums.offer(1);
nums.offer(8);
nums.offer(2);
nums.offer(-4);
System.out.println(nums.peek());
}
}
class CustomComparator implements Comparator<Integer>{
@Override
public int compare(Integer n1, Integer n2){
int val = n1.compareTo(n2);
if(val > 0)
return -1;
else if(val < 0)
return 1;
else
return 0;
}
}
n1.compareTo(n2) * (-1)
или n2.compareTo(n1)
в compare
методе
- person jscherman; 15.10.2020
Вы можете использовать MinMaxPriorityQueue
(это часть библиотеки Guava): вот документация. Вместо poll()
нужно вызвать метод pollLast()
.
Измените PriorityQueue на MAX PriorityQueue Метод 1: Очередь pq = new PriorityQueue ‹> (Collections.reverseOrder ()); Метод 2: очередь pq1 = new PriorityQueue ‹> ((a, b) -> b - a); Давайте посмотрим на несколько примеров:
public class Example1 {
public static void main(String[] args) {
List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.addAll(ints);
System.out.println("Priority Queue => " + pq);
System.out.println("Max element in the list => " + pq.peek());
System.out.println("......................");
// another way
Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
pq1.addAll(ints);
System.out.println("Priority Queue => " + pq1);
System.out.println("Max element in the list => " + pq1.peek());
/* OUTPUT
Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
......................
Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
*/
}
}
Возьмем известную задачу из интервью: K-й самый большой элемент в массиве с использованием PriorityQueue
public class KthLargestElement_1{
public static void main(String[] args) {
List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
int k = 3;
Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.addAll(ints);
System.out.println("Priority Queue => " + pq);
System.out.println("Max element in the list => " + pq.peek());
while (--k > 0) {
pq.poll();
} // while
System.out.println("Third largest => " + pq.peek());
/*
Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
Third largest => 666
*/
}
}
По-другому :
public class KthLargestElement_2 {
public static void main(String[] args) {
List<Integer> ints = Arrays.asList(222, 555, 666, 333, 111, 888, 777, 444);
int k = 3;
Queue<Integer> pq1 = new PriorityQueue<>((a, b) -> b - a);
pq1.addAll(ints);
System.out.println("Priority Queue => " + pq1);
System.out.println("Max element in the list => " + pq1.peek());
while (--k > 0) {
pq1.poll();
} // while
System.out.println("Third largest => " + pq1.peek());
/*
Priority Queue => [888, 444, 777, 333, 111, 555, 666, 222]
Max element in the list => 888
Third largest => 666
*/
}
}
Как видим, оба дают одинаковый результат.
Я только что провел симуляцию Монте-Карло на обоих компараторах при сортировке с двойной кучей min max, и они оба пришли к одному и тому же результату:
Это максимальные компараторы, которые я использовал:
(A) Сборки встроенного компаратора
PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder());
(B) Пользовательский компаратор
PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(new Comparator<Integer>() {
int compare(Integer lhs, Integer rhs) {
if (rhs > lhs) return +1;
if (rhs < lhs) return -1;
return 0;
}
});
if (rhs < lhs) return +1;
if (rhs ›lhs) return -1;
- person Tia; 10.02.2016
Вы можете попробовать что-то вроде:
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> -1 * Integer.compare(x, y));
Что работает для любой другой базовой функции сравнения, которая у вас может быть.
Вы можете попробовать толкать элементы с обратным знаком. Например: добавить a = 2 & b = 5, а затем опросить b = 5.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());
После опроса главы очереди измените знак для вашего использования. Это напечатает 5 (более крупный элемент). Может использоваться в наивных реализациях. Определенно ненадежное решение. Не рекомендую.
Используя lamda, просто умножьте результат на -1, чтобы получить очередь с максимальным приоритетом.
PriorityQueue<> q = new PriorityQueue<Integer>(
(a,b) -> -1 * Integer.compare(a, b)
);
b-a
может вызвать overflow
, поэтому следует избегать его использования и использовать Collections.reverseOrder();
в качестве компаратора или заменить b-a на Integer.compare(a,b);
, который был добавлен в Java 8
- person Yug Singh; 14.03.2019