Wie PriorityQueue in Java doppelte Einträge sortiert?

Question

Es klingt vielleicht albern, aber es macht Sinn, wenn Sie Objekt (Schlüssel, Wert) paar haben und Sie sie nach den Schlüsseln sortieren. Zu meinen Punkt mit Code veranschaulichen:

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? 
    } 
} 

Was in pair sein würde? Das erste oder letzte hinzugefügte Element? Oder irgendwelche von ihnen ohne Möglichkeit zu entscheiden?

Answer 1

Priorityqueue API macht keine Versprechungen für diese Situation:

Der Kopf dieser Warteschlange mit Bezug auf die angegebene Reihenfolge das kleinste Element ist. Wenn mehrere Elemente für den kleinsten Wert gebunden sind, ist der Kopf eines dieser Elemente - Bindungen sind willkürlich gebrochen. Die Warteschlangenabrufvorgänge rufen das Element am Kopf der Warteschlange ab, entfernen es, gucken und rufen das Element auf.

Aber es ist einfach zu testen. In toString zu paaren

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

und drucken Sie die Umfrage Ergebnis

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

druckt

1 1 

Answer 2

Grundsätzlich ist Queue firstInfirstOut Datenstruktur.

In PriorityQueue definiert die comparable -ity die Reihenfolge.

Wie bei Ihrem Fall Priorität aller Pair() sind gleich. daher keine Änderung in der Reihenfolge.

First-In-First-Out dh Pairs (1,1) (1,2) (1,3)

Wie pro documentation

Die poll Auslagerungen Warteschlange, entfernen, Peek und Elementzugriffs das Element an der Spitze der Warteschlange .