Mam kolejkę priorytetową w Javie Integers:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
Kiedy dzwonię pq.poll()
, otrzymuję element minimum.
Pytanie: jak zmienić kod, aby uzyskać maksymalny element?
Mam kolejkę priorytetową w Javie Integers:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
Kiedy dzwonię pq.poll()
, otrzymuję element minimum.
Pytanie: jak zmienić kod, aby uzyskać maksymalny element?
Odpowiedzi:
Co powiesz na to:
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()
Zapewnia Comparator
, że sortowania elementów w PriorityQueue
w w przeciwległy celu ich naturalnego porządku w tej sprawie.
Collections.reverseOrder()
jest również przeciążony, aby wziąć komparator, więc działa również, jeśli porównujesz obiekty niestandardowe.
PriorityQueue(Comparator<? super E> comparator)
.
Możesz używać wyrażenia lambda od wersji Java 8.
Poniższy kod wypisze 10, większy.
// 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());
Funkcja lambda weźmie dwie liczby całkowite jako parametry wejściowe, odejmie je od siebie i zwróci wynik arytmetyczny. Funkcja N realizuje interfejsu funkcjonalnego, Comparator<T>
. (Jest to używane w miejscu, w przeciwieństwie do klasy anonimowej lub dyskretnej implementacji).
(x, y) -> y - x
może nie być odpowiedni dla długich liczb całkowitych z powodu przepełnienia. Na przykład liczby y = Integer.MIN_VALUE i x = 5 dają w wyniku liczbę dodatnią. Lepiej jest użyć new PriorityQueue<>((x, y) -> Integer.compare(y, x))
. Jednak lepsze rozwiązanie daje @Edwin Dalorzo Collections.reverseOrder()
.
Możesz podać Comparator
obiekt niestandardowy, który klasyfikuje elementy w odwrotnej kolejności:
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;
}
});
Teraz kolejka priorytetowa odwróci wszystkie swoje porównania, więc otrzymasz element maksymalny, a nie element minimalny.
Mam nadzieję że to pomoże!
if (rhs < lhs) return +1;
if (rhs > lhs) return -1;
if (lhs < rhs) return +1; if (lhs > rhs) return -1;
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
new Comparator<Integer> () {
public int compare(Integer a, Integer b) {
return b - a;
}
}
);
b-a
może powodować overflow
tak powinny unikać go i stosować Collections.reverseOrder();
jako komparator lub wymienić ba z Integer.compare(a,b);
którego został dodanyJava 8
W Javie 8+ możesz utworzyć kolejkę z maksymalnym priorytetem za pomocą jednej z następujących metod:
Metoda 1:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
Metoda 2:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a);
Metoda 3:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a));
Elementy kolejki priorytetowej są porządkowane zgodnie z ich naturalną kolejnością lub przez Komparator dostarczany w czasie tworzenia kolejki.
Komparator powinien zastąpić metodę porównania.
int compare(T o1, T o2)
Domyślna metoda porównania zwraca ujemną liczbę całkowitą, zero lub dodatnią liczbę całkowitą, ponieważ pierwszy argument jest mniejszy, równy lub większy od drugiego.
Domyślna kolejka PriorityQueue dostarczana przez Javę to Min-Heap, jeśli chcesz, aby następowała maksymalna sterta, to kod
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());
}
}
}
Źródła: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator ()
Oto przykład Max-Heap w Javie:
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());
Wynik wyniesie 10
Można to osiągnąć za pomocą poniższego kodu w Javie 8, który wprowadził konstruktor, który pobiera tylko komparator.
PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
Możesz użyć MinMaxPriorityQueue
(jest to część biblioteki Guava):
oto dokumentacja . Zamiast tego poll()
musisz wywołać pollLast()
metodę.
Zmień PriorityQueue na MAX PriorityQueue Metoda 1: Kolejka pq = new PriorityQueue <> (Collections.reverseOrder ()); Metoda 2: Queue pq1 = new PriorityQueue <> ((a, b) -> b - a); Spójrzmy na kilka przykładów:
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
*/
}
}
Weźmy słynny wywiad Problem: Kth największy element w tablicy przy użyciu 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
*/
}
}
Inny sposób :
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
*/
}
}
Jak widać, oba dają ten sam wynik.
Właśnie przeprowadziłem symulację Monte-Carlo na obu komparatorach przy sortowaniu podwójnej sterty min max i oba otrzymały ten sam wynik:
Oto maksymalne komparatory, których użyłem:
(A) Wbudowany komparator kolekcji
PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder());
(B) Niestandardowy komparator
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;
Możesz spróbować czegoś takiego:
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> -1 * Integer.compare(x, y));
Która działa w przypadku każdej innej podstawowej funkcji porównania, którą możesz mieć.
PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));
Możesz spróbować popychać elementy ze znakiem odwrotnym. Np .: aby dodać a = 2 i b = 5, a następnie odpytać b = 5.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());
Po odpytaniu szefa kolejki odwróć znak dla swojego użycia. Spowoduje to wydrukowanie 5 (większy element). Może być używany w naiwnych realizacjach. Zdecydowanie nie jest to niezawodna poprawka. Nie polecam tego.
Możemy to zrobić, tworząc naszą klasę CustomComparator, która implementuje interfejs Comparator i nadpisując jej metodę porównania. Poniżej znajduje się kod tego samego:
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;
}
}