Ik heb een prioriteitswachtrij in Java van gehele getallen:
PriorityQueue<Integer> pq= new PriorityQueue<Integer>();
Als ik pq.poll() aanroep, krijg ik het minimumelement.
Vraag: hoe verander je de code om het maximale element te krijgen?
Antwoord 1, autoriteit 100%
Wat dacht je van dit:
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);
}
De Collections.reverseOrder() biedt een Comparator die de elementen in de PriorityQueue zou sorteren in een omgekeerde volgorde van hun natuurlijke volgorde in dit geval.
Antwoord 2, autoriteit 33%
Je kunt lambda-expressie gebruiken sinds Java 8.
De volgende code drukt 10 af, hoe groter.
// 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());
De lambda-functie neemt twee gehele getallen als invoerparameters, trekt ze van elkaar af en retourneert het rekenkundige resultaat. De lambda-functie implementeert de functionele interface, Comparator<T>. (Dit wordt op zijn plaats gebruikt, in tegenstelling tot een anonieme klasse of een discrete implementatie.)
Antwoord 3, autoriteit 11%
In Java 8+ kunt u een wachtrij met maximale prioriteit maken via een van deze methoden:
Methode 1:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
Methode 2:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b - a);
Methode 3:
PriorityQueue<Integer> maxPQ = new PriorityQueue<>((a,b) -> b.compareTo(a));
Antwoord 4, autoriteit 10%
U kunt een aangepast Comparator-object opgeven dat elementen in omgekeerde volgorde rangschikt:
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;
}
});
Nu zal de prioriteitswachtrij alle vergelijkingen omkeren, zodat u het maximumelement krijgt in plaats van het minimumelement.
Hopelijk helpt dit!
Antwoord 5, autoriteit 5%
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
new Comparator<Integer> () {
public int compare(Integer a, Integer b) {
return b - a;
}
}
);
Antwoord 6, autoriteit 3%
De elementen van de prioriteitswachtrij worden geordend volgens hun natuurlijke volgorde, of door een comparator die wordt verstrekt tijdens de bouwtijd van de wachtrij.
De vergelijker moet de vergelijkingsmethode overschrijven.
int compare(T o1, T o2)
Standaard vergelijkingsmethode retourneert een negatief geheel getal, nul of een positief geheel getal, aangezien het eerste argument kleiner is dan, gelijk is aan of groter is dan het tweede.
De standaard PriorityQueue van Java is Min-Heap. Als u een maximale heap wilt, volgt u de code
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());
}
}
}
Referentie:https:// docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()
Antwoord 7, autoriteit 2%
We kunnen dit doen door onze klasse CustomComparator te maken die de Comparator-interface implementeert en de vergelijkingsmethode overschrijft. Hieronder staat de code voor hetzelfde:
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;
}
}
Antwoord 8
Hier is een voorbeeld van Max-Heap in 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());
De uitvoer is 10
Antwoord 9
Dit kan worden bereikt door de onderstaande code in Java 8 die een constructor heeft geïntroduceerd die alleen een comparator nodig heeft.
PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
Antwoord 10
Dit kan worden bereikt door
. te gebruiken
PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
Antwoord 11
Je kunt MinMaxPriorityQueue gebruiken (het maakt deel uit van de Guava-bibliotheek):
hier is de documentatie. In plaats van poll() moet je de methode pollLast() aanroepen.
Antwoord 12
Wijzig PriorityQueue in MAX PriorityQueue
Methode 1: Wachtrij pq = nieuwe PriorityQueue<>(Collections.reverseOrder());
Methode 2: Wachtrij pq1 = nieuwe PriorityQueue<>((a, b) -> b – a);
Laten we een paar voorbeelden bekijken:
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
*/
}
}
Laten we een beroemd interview nemen
Probleem: Kth grootste element in een array met 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
*/
}
}
Andere manier:
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
*/
}
}
Zoals we kunnen zien, geven beide hetzelfde resultaat.
Antwoord 13
Ik heb zojuist een Monte-Carlo-simulatie uitgevoerd op beide comparators op dubbele heap sort min max en ze kwamen allebei tot hetzelfde resultaat:
Dit zijn de max. vergelijkers die ik heb gebruikt:
(A) Ingebouwde vergelijkingsfunctie voor verzamelingen
PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder());
(B) Aangepaste vergelijker
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;
}
});
Antwoord 14
Je kunt iets proberen als:
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> -1 * Integer.compare(x, y));
Wat werkt voor elke andere basisvergelijkingsfunctie die u mogelijk heeft.
Antwoord 15
PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));
Antwoord 16
Je kunt proberen om elementen met een omgekeerd teken te duwen. Bijv.: Om a=2 & b=5 en dan poll b=5.
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(-a);
pq.add(-b);
System.out.print(-pq.poll());
Zodra u de kop van de wachtrij hebt ondervraagd, keert u het bord om voor uw gebruik.
Dit zal 5 (groter element) afdrukken. Kan worden gebruikt in naïeve implementaties. Absoluut geen betrouwbare oplossing. Ik raad het niet aan.
Antwoord 17
Gebruik lamda, vermenigvuldig het resultaat met -1 om de maximale prioriteitswachtrij te krijgen.
PriorityQueue<> q = new PriorityQueue<Integer>(
(a,b) -> -1 * Integer.compare(a, b)
);