Java: PriorityQueue retourne une commande incorrecte du comparateur personnalisé?

Question

J'ai écrit un comparateur personnalisé pour comparer mes classes de nœuds, mais la file d'attente de priorité java ne renvoie pas mes éléments dans le bon ordre.

Voici mon comparateur:

public int compare(Node n1, Node n2){ 

    if (n1.getF() > n2.getF()){ 
     return +1; 
    } 
    else if (n1.getF() < n2.getF()){ 
     return -1; 
    } 
    else { // equal 
     return 0; 
    } 
} 

Où getf retourne un double. Cependant après avoir inséré plusieurs noeuds dans la file d'attente prioritaire, je les imprimer à l'aide:

while(open.size() > 0) { 
    Node t = (Node)(open.remove()); 
    System.out.println(t.getF()); 
} 

qui se traduit par:

6.830951894845301 
6.830951894845301 
6.0 
6.0 
5.242640687119285 
7.4031242374328485 
7.4031242374328485 
8.071067811865476 

Toutes les idées pourquoi il en est ainsi? Mon comparateur est-il mauvais? Merci.

Mike

Answer 1

Comment imprimez-vous ces valeurs? Je ne pense pas que le iterator de PriorityQueue offre les mêmes garanties de commande que la classe globale fait, et donc potentiellement si vous faites

for(Node n : queue) { 
System.out.println(n.getF()); 
} 

Vous allez recevoir la sortie non numérotée. L'assurance de commande ne s'applique qu'à offer, take, poll, peek, et éventuellement à d'autres méthodes.

Il y a une mention spéciale sur la iterator dans les javadocs pour la file d'attente prioritaire http://java.sun.com/javase/6/docs/api/java/util/PriorityQueue.html

Answer 2

Je ne sais pas quel est le problème avec votre code, mais cela fonctionne pour moi:

import java.util.*; 
public class Test { 
    public static void main(String[] args) { 
     PriorityQueue<Node> open = new PriorityQueue<Node>(10, 
       new Comparator<Node>() { 
      @Override 
      public int compare(Node n1, Node n2){ 
       if (n1.getF() > n2.getF()){ 
        return +1; 
       } 
       else if (n1.getF() < n2.getF()){ 
        return -1; 
       } 
       else { // equal 
        return 0; 
       } 
      } 
     }); 

     for (int i = 0; i < 20; i++) 
      open.add(new Node()); 

     while(open.size() > 0) { 
      Node t = (Node)(open.remove()); 
      System.out.println(t.getF()); 
     } 
    } 
} 

class Node { 
    double d = Math.random() * 10; 
    public double getF() { return d; } 
} 

Sortie:

0.21442281608773262 
1.9965384843480016 
2.6660026888929824 
2.888889937975976 
3.098932914222398 
3.1059072964534638 
4.193212975907516 
4.296282412431935 
4.3241392173963735 
4.825876226139123 
5.193550353435191 
5.637831708672641 
5.949759449054407 
6.620639629878806 
7.505126870725806 
7.966337123623846 
8.270840212631589 
8.484502118941545 
8.730910327480023 
9.191324325662219 

Assurez-vous que getF() ne retourne pas accidentellement une version int du double.

---

Mise à jour: Vous ne pouvez pas mettre à jour les données qui définissent l'ordre des éléments après l'insertion. Dans ce cas, vous devez extraire l'élément, le mettre à jour et le réinsérer.