Les objets ajoutés à une priorité de la Priority ne sont pas commandés par leur priorité

Question

J'essaie d'implémenter un tas en utilisant une priorité de priorité comme suit:

PriorityQueue<Node> heap = new PriorityQueue<Node>();
Set<String> allWords = codebook.getAllWords();
for(String word : allWords)
{
    heap.add(new Node(word, codebook.getProbability(word)));
    System.out.println(heap.toString());
}

Où j'ai défini le nœud comme une classe privée à l'intérieur de la même classe qui contient la méthode ci-dessus. Le nœud est défini comme:

private static class Node implements Comparable
{
    protected Node left;
    protected Node right;
    protected String name;
    protected double frequency;
    public Node(String n, double f)
    {
        name = n;
        frequency = f;
    }
    public Node(double f, Node l, Node r)
    {
        frequency = f;
        left = l;
        right = r;
    }

    @Override
    public int compareTo(Object arg0) 
    {
        Node other = (Node)(arg0);
        if(this.frequency < other.frequency)
        {
            System.out.println(name + " < " + other.name);
            return -1;
        }
        else if(this.frequency > other.frequency)
        {
            System.out.println(name + " > " + other.name);
            return 1;
        }
        System.out.println(name + " is equal to " + other.name);
        return 0;
    }

    public String toString()
    {return name;}
}

Cependant, lorsque j'ajoute des nœuds à la PriorityQueue, ils ne sont pas commandés par fréquence. Sur la base de la sortie de mes instructions println, les valeurs correctes sont renvoyées par Node.compareto (). Par exemple, étant donné l'ensemble de données:

• nom, fréquence
• besoin, 3
• chat, 1
• soigné, 2

Mon code produit:
// Ajouter le besoin
besoin
// Ajouter un chat
chat <besoin
Cat, besoin
// Ajouter soigné
Neat> chat
Cat, besoin, soigné
Lorsque la Priorityqueue doit être [chat, soignée, besoin
Des conseils sur la raison pour laquelle cela se produit?

Answer 1

La commande d'un itérateur pour PriorityQueue n'est pas défini; la commande lors de l'appel poll() devrait être l'ordre du comparateur. À partir de la spécification de l'API,

iterator() Renvoie un itérateur sur les éléments de cette file d'attente. L'itérateur ne renvoie pas les éléments dans un ordre particulier.

Si ce dont vous avez vraiment besoin est un ensemble trié, utilisez SortedSet Ou mettre les choses dans une collection et utiliser Collections.sort(). Si, cependant, vous avez vraiment besoin d'un pqueue, voici mon exemple de correction:

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Set;


public class TestPriorityQueue 
{
  static Map<String,Double> codebook = new HashMap<String, Double>();
  static {
    codebook.put("need", 3.0);
    codebook.put("cat", 1.0);
    codebook.put("neat", 2.0);
  }

  public static void main(String[] args)
  {
    test();
  }

  public static void test() {
    PriorityQueue<Node> heap = new PriorityQueue<Node>();
    Set<String> allWords = codebook.keySet();
    for (String word : allWords) {
      heap.add(new Node(word, codebook.get(word)));
      System.out.println(heap.toString());
    }

    System.out.println("In order now:");
    while(!heap.isEmpty()) {
      System.out.println(heap.poll());
    }
  }

  private static class Node implements Comparable<Node>
  {
      protected Node left;
      protected Node right;
      protected String name;
      protected double frequency;
      public Node(String n, double f)
      {
          name = n;
          frequency = f;
      }
      public Node(double f, Node l, Node r)
      {
          frequency = f;
          left = l;
          right = r;
      }

      @Override
      public int compareTo(Node arg0) 
      {
          if(this.frequency < arg0.frequency)
          {
              System.out.println(name + " < " + arg0.name);
              return -1;
          }
          else if(this.frequency > arg0.frequency)
          {
              System.out.println(name + " > " + arg0.name);
              return 1;
          }
          System.out.println(name + " is equal to " + arg0.name);
          return 0;
      }

      public String toString()
      {return name;}
  }

}

Donne:

[need]
cat < need
[cat, need]
neat > cat
[cat, need, neat]
In order now:
neat < need
cat
neat
need

Answer 2

Les priorités de priorités fonctionnent sur une base "juste à temps". Si vous affichez simplement leur contenu, le contenu ne sera pas dans l'ordre trié; Ils sont dans un tas (ce qui, puisque vous avez mentionné, je pense que vous le sauriez.) Quoi qu'il en soit, pour remettre le contenu en ordre, vous devez retirer les articles un à la fois avec I Poll ().