Jak PriorityQueue w Java sortuje duplikaty wpisów?

Question

Może to zabrzmieć głupio, ale ma sens, gdy masz obiekt pary (klucza, wartości) i sortujesz je według kluczy. Aby zilustrować mój punkt z kodem:

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

Co będzie w pair? Pierwszy lub ostatni dodany element? A może któryś z nich bez możliwości decydowania?

Answer 1

kolejka priorytetowa API nie składa żadnych obietnic w tej sytuacji:

Szef tej kolejki jest najmniejszym elementem w odniesieniu do określonego zamówienia. Jeśli wiele elementów jest powiązanych z najmniejszą wartością, głowa jest jednym z tych elementów - krawędzie są arbitralnie łamane. Ankiety pobierania, usuwania, podglądu i elementu w kolejce umożliwiają dostęp do elementu znajdującego się na początku kolejki.

Ale łatwo to przetestować. Dodaj toString parowanie

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

i wydrukować wynik ankietę

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

drukuje

1 1 

Answer 2

Zasadniczo Queue jest pierwszą strukturą danych FirstInForstOut.

W PriorityQueue: comparable -ity określa kolejność.

Podobnie jak w przypadku Twojego przypadku wszystkie numery Pair() są takie same. stąd żadna zmiana w porządku.

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

Zgodnie documentation

Kolejka operacji pobierania sondzie, usuwanie, peek, a dostęp elementem elementu na czele kolejki .