Ändern Sie priorityQueue in max priorityqueue

122

Ich habe Prioritätswarteschlange in Java von Ganzzahlen:

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

Wenn ich anrufe, pq.poll()bekomme ich das minimale Element.

Frage: Wie ändere ich den Code, um das maximale Element zu erhalten?

Borut Flis
quelle
4
Ich denke, Sie sollten den Konstruktor verwenden, der dafür einen Komparator erhält. Verwenden Sie den Collections.reverseOrder, um einen umgekehrten Komparator zu erhalten.
Edwin Dalorzo
1
Sie müssen einen Komparator übergeben. siehe stackoverflow.com/questions/683041/…
DarthVader
Dies könnte helfen: tech693.blogspot.com/2018/09/…
Java Guru

Antworten:

232

Wie wäre es so:

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

Das Collections.reverseOrder()sieht vor, Comparatordass die Elemente in der PriorityQueueentgegengesetzten Reihenfolge in ihrer natürlichen Reihenfolge in diesem Fall sortiert werden.

Edwin Dalorzo
quelle
14
Collections.reverseOrder()ist auch überladen, um einen Komparator zu verwenden, sodass es auch funktioniert, wenn Sie benutzerdefinierte Objekte vergleichen.
fliegende Schafe
14
PriorityQueue von Java 8 verfügt über einen neuen Konstruktor, der nur den Komparator als Argument verwendet PriorityQueue(Comparator<? super E> comparator).
Abhisheknirmal
75

Sie können den Lambda-Ausdruck seit Java 8 verwenden.

Der folgende Code gibt 10 aus, je größer.

// 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());

Die Lambda-Funktion verwendet zwei Ganzzahlen als Eingabeparameter, subtrahiert sie voneinander und gibt das arithmetische Ergebnis zurück. Die Lambda-Funktion implementiert die Funktionsschnittstelle Comparator<T>. (Dies wird an Ort und Stelle verwendet, im Gegensatz zu einer anonymen Klasse oder einer diskreten Implementierung.)

Guangtong Shen
quelle
Die Lambda-Funktion benennt ihre Eingabeparameter x und y und gibt yx zurück. Dies ist im Grunde das, was die int-Komparatorklasse tut, außer dass sie xy zurückgibt
Edi Bice
15
Der Komparator like ist (x, y) -> y - xaufgrund des Überlaufs möglicherweise nicht für lange Ganzzahlen geeignet. Zum Beispiel ergeben die Zahlen y = Integer.MIN_VALUE und x = 5 eine positive Zahl. Es ist besser zu benutzen new PriorityQueue<>((x, y) -> Integer.compare(y, x)). Die bessere Lösung wird jedoch von @Edwin Dalorzo zur Verfügung gestellt Collections.reverseOrder().
Гима Гирин
1
@ ФимаГирин Das stimmt. -2147483648 - 1 wird 2147483647
Guangtong Shen
27

Sie können ein benutzerdefiniertes ComparatorObjekt bereitstellen , das Elemente in umgekehrter Reihenfolge ordnet:

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

Jetzt kehrt die Prioritätswarteschlange alle Vergleiche um, sodass Sie das maximale Element anstelle des minimalen Elements erhalten.

Hoffe das hilft!

templatetypedef
quelle
5
vielleicht für eine maximale Priorität q die lhs <rhs zurück +1; Was Sie hier geschrieben haben, ist das Minimum q nach meinen Tests
Sivi
Für den umgekehrten Druck, dh wenn die höchsten Elemente zuerst in einer Prioritätswarteschlange gedruckt werden sollen, sollte dies seinif (rhs < lhs) return +1; if (rhs > lhs) return -1;
Tia
@ Diksha Ich glaube, der Code, den ich habe, entspricht dem, was Sie posten. Ich habe nur die Beziehung größer als kleiner als verwendet.
Templatetypedef
4
Eigentlich mein Fehler. Ich meinte, es sollte so sein:if (lhs < rhs) return +1; if (lhs > rhs) return -1;
Tia
1
@ ShrikantPrabhu Guter Fang - das ist jetzt behoben!
Templatetypedef
14
PriorityQueue<Integer> pq = new PriorityQueue<Integer> (
  new Comparator<Integer> () {
    public int compare(Integer a, Integer b) {
       return b - a;
    }
  }
);
Varun Juneja
quelle
Was ist das Problem ?
CMedina
Dies ist perfekt und macht genau das, was gefragt wurde, indem aus einem Min-Heap ein Max-Heap wird.
Kamran
2
Verwenden b-akann dazu führen overflow, sollte es vermeiden, es zu verwenden und sollte Collections.reverseOrder();als Komparator verwendet werden oder ba ersetzen, mit Integer.compare(a,b);dem inJava 8
Yug Singh
9

In Java 8+ können Sie eine Warteschlange mit maximaler Priorität über eine der folgenden Methoden erstellen:

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)); 
Apadana
quelle
8

Die Elemente der Prioritätswarteschlange werden gemäß ihrer natürlichen Reihenfolge oder von einem Komparator geordnet, der zur Zeit der Warteschlangenerstellung bereitgestellt wird.

Der Komparator sollte die Vergleichsmethode überschreiben.

int compare(T o1, T o2)

Die Standardvergleichsmethode gibt eine negative Ganzzahl, Null oder eine positive Ganzzahl zurück, da das erste Argument kleiner, gleich oder größer als das zweite ist.

Die von Java bereitgestellte Standardprioritäts-Warteschlange ist Min-Heap. Wenn Sie einen maximalen Heap wünschen, folgt der folgende 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 ()

Rohan
quelle
4

Hier ist ein Beispiel für 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());

Die Ausgabe wird 10 sein

Nobal
quelle
4

Dies kann durch den folgenden Code in Java 8 erreicht werden, der einen Konstruktor eingeführt hat, der nur einen Komparator benötigt.

PriorityQueue<Integer> maxPriorityQ = new PriorityQueue<Integer>(Collections.reverseOrder());
Anshu Shekhar
quelle
3

Sie können verwenden MinMaxPriorityQueue(es ist ein Teil der Guava-Bibliothek): Hier ist die Dokumentation . Stattdessen poll()müssen Sie die pollLast()Methode aufrufen .

Chthonisches Projekt
quelle
3

Ändern Sie PriorityQueue in MAX PriorityQueue Methode 1: Queue pq = new PriorityQueue <> (Collections.reverseOrder ()); Methode 2: Warteschlange pq1 = neue PriorityQueue <> ((a, b) -> b - a); Schauen wir uns einige Beispiele an:

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

         */


    }
}

Nehmen wir ein berühmtes Interview Problem: Kth größtes Element in einem Array mit 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

 */
    }
}

Ein anderer Weg :

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

         */
    }
}

Wie wir sehen können, liefern beide das gleiche Ergebnis.

Soudipta Dutta
quelle
3

Dies kann durch Verwendung erreicht werden

PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
Ajinkya_M
quelle
1

Ich habe gerade eine Monte-Carlo-Simulation für beide Komparatoren mit Doppelhaufen-Sortierung min max durchgeführt und beide kamen zu demselben Ergebnis:

Dies sind die maximalen Komparatoren, die ich verwendet habe:

(A) Eingebauter Komparator für Sammlungen

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

(B) Benutzerdefinierter 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;
    }
});
sivi
quelle
Beim umgekehrten Drucken, if (rhs < lhs) return +1;dh wenn die höchsten Elemente zuerst in einer Prioritätswarteschlange gedruckt werden sollen, sollte dies der Fall sein, wenn (rhs> lhs) -1 zurückgibt.
Tia
Sie können es bearbeiten, wenn Sie möchten. Ich habe keine Zeit zu bestätigen, was Sie geschrieben haben. In meinem Setup war das, was ich geschrieben habe, korrekt
sivi
1

Sie können etwas versuchen wie:

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

Was für jede andere Basisvergleichsfunktion funktioniert, die Sie möglicherweise haben.

Horia Coman
quelle
1
PriorityQueue<Integer> lowers = new PriorityQueue<>((o1, o2) -> -1 * o1.compareTo(o2));
Sumit Kumar Saha
quelle
0

Sie können versuchen, Elemente mit umgekehrtem Vorzeichen zu drücken. Beispiel: Addiere a = 2 & b = 5 und frage dann b = 5 ab.

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

Wenn Sie den Kopf der Warteschlange abgefragt haben, kehren Sie das Vorzeichen für Ihre Verwendung um. Dies druckt 5 (größeres Element). Kann in naiven Implementierungen verwendet werden. Auf keinen Fall eine zuverlässige Lösung. Ich empfehle es nicht.

Stürmer28
quelle