Change CodaConPriorita a max CodaConPriorita

Question

devo coda di priorità in Java di interi:

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

Quando chiamo pq.poll() ottengo l'elemento minimo.

Domanda: come modificare il codice per ottenere l'elemento massimo?

Answer 1

Come su come questo:

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

Il Collections.reverseOrder() fornisce una Comparator che ordinare gli elementi nel PriorityQueue in un ordine oposite al loro ordine naturale in questo caso.

Answer 2

è possibile fornire un personalizzato Comparator oggetto che si colloca in ordine inverso:

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

Ora, la coda di priorità invertirà tutti i suoi confronti, in modo da otterrete l'elemento massimo, piuttosto che l'elemento minimo.

Spero che questo aiuti!

Answer 3

È possibile utilizzare MinMaxPriorityQueue (è parte della libreria Guava): here's the documentation. Invece di poll(), è necessario chiamare il metodo pollLast().

Answer 4

Ecco un esempio 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()); 

l'uscita sarà il 10

Answer 5

Ho appena eseguito una simulazione Monte-Carlo su entrambi i comparatori sulle doppie mucchio sorta minimo massimo ed entrambi è venuto allo stesso risultato:

Questi sono i comparatori max che ho usato:

Collezioni (a) built-in di confronto

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

(B) su misura comparatore

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

Si può cercare elementi con segno inverso a spingere. Ad es .: aggiungere a = 2 & b = 5 e quindi eseguire il sondaggio b = 5.

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

Dopo aver eseguito il polling alla testa della coda, invertire il segno per l'utilizzo. Questo stamperà 5 (elemento più grande). Può essere utilizzato in implementazioni ingenue. Sicuramente non è una soluzione affidabile. Non lo consiglio

Answer 8

È possibile utilizzare un'espressione lambda dal Java 8.

Il codice seguente stamperà 10, il più grande.

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

La funzione lambda avrà due interi come parametri di input, li sottrarre l'uno dall'altro, e restituire il risultato aritmetica.La funzione lambda implementa l'interfaccia funzionale, Comparator<T>. (Questo è usato in luogo, al contrario di una classe anonima o un'implementazione discreta.)

Answer 9

Gli elementi della coda di priorità vengono ordinati in base al loro ordinamento naturale o da un comparatore fornito in fase di costruzione della coda.

Il comparatore deve sovrascrivere il metodo di confronto.

int compare(T o1, T o2) 

predefinita confronta metodo restituisce un intero negativo, zero o un numero intero positivo come primo argomento è minore, uguale o maggiore del secondo.

Il CodaConPriorita predefinito fornito da Java è Min-Mucchio, se volete un mucchio max seguito è il codice

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

} 

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

Answer 10

Si può provare qualcosa di simile:

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

Che funziona per qualsiasi altra funzione di confronto di base che si possa avere.