Zmień PriorityQueue na max Priorityqueue


124

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?


4
Myślę, że powinieneś użyć konstruktora, który otrzymuje do tego komparator. Użyj kolekcji Collections.reverseOrder, aby uzyskać odwrócony komparator.
Edwin Dalorzo

1
musisz zdać komparator. patrz stackoverflow.com/questions/683041/…
DarthVader

Odpowiedzi:


232

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 PriorityQueuew w przeciwległy celu ich naturalnego porządku w tej sprawie.


14
Collections.reverseOrder()jest również przeciążony, aby wziąć komparator, więc działa również, jeśli porównujesz obiekty niestandardowe.
latające owce

14
PriorityQueue w Javie 8 ma nowy konstruktor, który jako argument przyjmuje po prostu komparator PriorityQueue(Comparator<? super E> comparator).
abhisheknirmal

75

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).


funkcja lambda, nazywa swoje parametry wejściowe xiy i zwraca yx, co jest w zasadzie tym, co robi klasa porównawcza int, z wyjątkiem tego, że zwraca xy
Edi Bice

15
Taki komparator (x, y) -> y - xmoż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().
Фима Гирин

1
@ ФимаГирин To prawda. -2147483648 - 1 staje się 2147483647
Guangtong Shen

27

Możesz podać Comparatorobiekt 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!


5
może dla maksymalnego priorytetu q lewa oś <prawa oś returs +1; co tu napisałeś to minimum q po moich testach
sivi

W przypadku druku odwrotnego, czyli jeśli najwyższe elementy mają być drukowane jako pierwsze w kolejce priorytetowej, powinno to byćif (rhs < lhs) return +1; if (rhs > lhs) return -1;
Tia

@Diksha Uważam, że kod, który mam, jest odpowiednikiem tego, co piszesz. Po prostu użyłem relacji większy niż, a nie mniej niż.
templatetypedef

4
właściwie, mój błąd .. Chodziło mi o to, że powinno być tak:if (lhs < rhs) return +1; if (lhs > rhs) return -1;
Tia

1
@ShrikantPrabhu Dobry chwyt - to już naprawione!
templatetypedef

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

Jaki jest problem ?
CMedina

Jest to idealne rozwiązanie i robi dokładnie to, o co proszono, zamieniając minimalny stos w maksymalny stos.
Kamran

2
stosując b-amoże powodować overflowtak powinny unikać go i stosować Collections.reverseOrder();jako komparator lub wymienić ba z Integer.compare(a,b);którego został dodanyJava 8
Yug Singh

10

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

8

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


4

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


4

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


3

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.


3

Można to osiągnąć za pomocą

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

1

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

W przypadku drukowania odwrotnego, czyli jeśli najwyższe elementy mają być drukowane jako pierwsze w kolejce priorytetowej, powinno to być if (rhs < lhs) return +1;if (rhs> lhs) return -1;
Tia

Możesz go edytować, jeśli chcesz. Nie mam czasu na potwierdzenie tego, co napisałeś. W mojej konfiguracji to, co napisałem, było poprawne
sivi

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ć.



0

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.


0

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;
    }
}
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.