ändern Priorityqueue bis max Priorityqueue

Question

Ich habe Prioritätswarteschlange in Java ganzen Zahlen:

PriorityQueue<Integer> pq= new PriorityQueue<Integer>(); 

Als ich pq.poll() nenne ich das kleinste Element erhalten.

Frage: Wie man den Code ändert, um das maximale Element zu erhalten?

Answer 1

Wie wäre es wie folgt aus:

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); 
} 

Die Collections.reverseOrder() ein Comparator bereitstellt, die die Elemente in der PriorityQueue in einer der oposite, um ihre natürliche Ordnung in diesem Fall sortieren würde.

Answer 2

Sie können eine benutzerdefinierte Comparator Objekt zur Verfügung stellen, die in der umgekehrten Reihenfolge zählt:

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(defaultSize, new Comparator<Integer>() { 
    int compare(Integer lhs, Integer rhs) { 
     if (lhs > rhs) return +1; 
     if (lhs.equals(rhs)) return 0; 
     return -1; 
    } 
}); 

die Prioritätswarteschlange wird nun alle seine Vergleiche umkehren, so dass Sie nicht das maximale Element erhalten wird als das kleinste Element.

Hoffe, das hilft!

Answer 3

Sie können MinMaxPriorityQueue verwenden (es ist ein Teil der Guava-Bibliothek): here's the documentation. Anstelle von poll() müssen Sie die pollLast() Methode aufrufen.

Answer 4

Hier ein Beispiel 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()); 

wird der Ausgang 10 sein

Answer 5

Ich lief eine Monte-Carlo-Simulation auf beiden Komparatoren auf Doppelstapelsortier-min max und sie beide kam zu dem gleichen Ergebnis:

Dies sind die Komparatoren max ich verwendet habe:

(A) Sammlungen eingebauter Komparator

PriorityQueue<Integer> heapLow = new PriorityQueue<Integer>(Collections.reverseOrder()); 

(B) Individuelle 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; 
    } 
}); 

Answer 6

PriorityQueue<integer> pq = new PriorityQueue<integer> (
    new Comparator<integer>() { 
    public int compare(Integer a, Integer b) { 
     return b - a; 
    } 
    } 
); 

Answer 7

Sie können versuchen, Elemente mit umgekehrtem Vorzeichen schieben. ZB: Um a = 2 & b = 5 und dann poll b = 5.

PriorityQueue<Integer> pq = new PriorityQueue<>(); 
pq.add(-a); 
pq.add(-b); 
System.out.print(-pq.poll()); 

Sobald Sie den Kopf der Warteschlange abgefragt haben, kehren Sie das Zeichen für Ihre Verwendung um. Dies wird 5 drucken (größeres Element). Kann in naiven Implementierungen verwendet werden. Definitiv keine zuverlässige Lösung. Ich empfehle es nicht.

Answer 8

können Sie Lambda-Ausdruck, da Java verwenden 8.

Der folgende Code wird 10 drucken, desto größer ist.

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x); 
pq.add(10); 
pq.add(5); 
System.out.println(pq.peek()); 

Die Lambda-Funktion wird zwei ganze Zahlen als Eingangsparameter nehmen, um sie voneinander subtrahieren, und gibt das arithmetische Ergebnis.Die Lambda-Funktion implementiert das Funktionsinterface Comparator<T>. (Dies wird anstelle einer anonymen Klasse oder einer diskreten Implementierung verwendet.)

Answer 9

Die Elemente der Prioritätswarteschlange werden nach ihrer natürlichen Reihenfolge geordnet oder von einem Comparator, der zum Zeitpunkt der Warteschlangenerstellung bereitgestellt wird.

Der Komparator sollte die Vergleichsmethode überschreiben.

int compare(T o1, T o2) 

Standard vergleichen Methode eine negative ganze Zahl zurückgibt, Null oder eine positive ganze Zahl als das erste Argument kleiner als, gleich oder größer als der zweite.

Der Standard Priorityqueue von Java zur Verfügung gestellt ist Min-Heap, Wenn Sie eine max Heap wollen finden Sie den 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()); 
     } 
    } 

} 

Referenz: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#comparator()

Answer 10

Sie können wie etwas versuchen:

PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> -1 * Integer.compare(x, y)); 

Das funktioniert für jede andere Basisvergleichsfunktion, die Sie haben könnten.