In che modo PriorityQueue in Java ordina le voci duplicate?

Question

Può sembrare sciocco, ma ha senso quando si ha oggetto di coppia (chiave, valore) e li si ordina in base ai tasti. Per illustrare il mio punto con il codice:

public class Pair implements Comparable<Pair> { 
    private int value; 
    private int key; 

    public Pair(int key, int value) { 
     this.key = key; 
     this.value = value; 
    } 

    @Override 
    public int compareTo(Pair o) { 
     if (this.key > o.key) 
      return 1; 
     else if (this.key < o.key) 
      return -1; 
     return 0; 
    } 
} 

public class program { 
    public static void main(String[] args) { 
     PriorityQueue<Pair> queue = new PriorityQueue<Pair>; 
     queue.add(new Pair(1,1)); 
     queue.add(new Pair(1,2)); 
     queue.add(new Pair(1,3)); 

     Pair pair = queue.poll(); // What would be in pair? 
    } 
} 

Quale sarebbe in pair? Il primo o l'ultimo elemento aggiunto? O qualcuno di loro senza possibilità di decidere?

Answer 1

CodaConPriorita API fa promesse per questa situazione:

La testa di questa coda è l'elemento meno rispetto all'ordinamento specificato. Se più elementi sono legati per il minor valore, la testa è uno di questi elementi - i legami sono suddivisi in modo arbitrario. Le operazioni di recupero della coda eseguono il polling, la rimozione, l'occhiata e l'elemento di accesso all'elemento all'inizio della coda.

Ma è facile da testare. Aggiungere toString Per accoppiare

@Override 
public String toString() { 
    return key + " " + value; 
} 

e stampare il risultato del sondaggio

Pair pair = queue.poll(); // What would be in pair? 
    System.out.println(pair); 

esso stampa

1 1 

Answer 2

Fondamentalmente un Queue è la prima struttura dati First in First.

In PriorityQueue il comparable -ity definisce l'ordine.

Come nel caso, la priorità di tutti gli Pair() è la stessa. quindi nessun cambiamento in ordine.

First-In-First-Out cioè Pairs (1,1) (1,2) (1,3)

Come per documentation

Le operazioni di recupero coda di sondaggio, rimuovere, sbirciatina, e l'accesso elemento l'elemento alla testa della coda .