PriorityQueue trié mais les deux plus grands [doublons]

Nov 25 2020
public class Pair implements Comparable<Pair>{
    public String name;
    public int number;

    public int compareTo(Pair other) {
        if (other == null) {
            return 1;
        }
        return Integer.compare(number, other.number);
    }
}
ht = new Hashtable<String, Pair>(perLen);
PriorityQueue<Pair> pq = new PriorityQueue<Pair>(k);
set = ht.keySet();
for (String i: set) {
        tmp0 = ht.get(i);
        if (tmp0.compareTo(pq.peek()) > 0) {
            if (pq.size() == k) {
                pq.remove();
            }
            pq.add(tmp0);
        }
}
System.out.println(pq.toString());

PRODUCTION:

[OSCAR 822, ALBERTO 827, DAVID 1523, JAVIER 943]

Je recherche les k plus grandes paires (leur nombre) dans la table de hachage et celles de la sortie sont en fait les bonnes. Ma question est la suivante: pourquoi les deux derniers sont-ils échangés?

Réponses

2 fps Nov 25 2020 at 11:38

PriorityQueuene renvoie que l'élément le plus bas de sa tête. Il ne trie pas tous les éléments, donc si vous parcourez la file d'attente avec pq.toString(), les éléments peuvent ne pas apparaître dans l'ordre. Cela se produit car, en interne, PriorityQueue.toString()utilise la PriorityQueue.iterator()méthode et, selon la documentation:

Il iterator()n'est pas garanti que l' itérateur fourni dans la méthode traverse les éléments de la file d'attente prioritaire dans un ordre particulier. Si vous avez besoin d'un parcours ordonné, pensez à utiliser Arrays.sort(pq.toArray()).

Si vous souhaitez imprimer les éléments de la file d'attente prioritaire dans l'ordre, vous devez modifier ce code:

System.out.println(pq.toString());

Aux suivants:

while (!pq.isEmpty()) 
    System.out.println(pq.remove());
1 BrightSoul Nov 25 2020 at 11:32

La méthode toString () de la classe PriorityQueue ne vous garantit pas l'ordre des éléments car elle utilise un itérateur.

Ashish Nov 25 2020 at 11:28

Vous pouvez vérifier la commande en utilisant la méthode de sondage comme ici:

Imprimer le contenu de la file d’attente prioritaire [java]