Объекты, добавленные в PriorityQueue, не упорядочены по приоритету. - PullRequest
Новая
       19

Объекты, добавленные в PriorityQueue, не упорядочены по приоритету.

3 голосов
/ 29 марта 2011

Я пытаюсь реализовать кучу с помощью PriorityQueue следующим образом: 

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());
}

Где я определил Node как закрытый класс внутри того же класса, который содержит вышеуказанный метод. Узел определен как: 

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

Однако, когда я добавляю узлы в PriorityQueue, они не упорядочены по частоте. Основываясь на выводе из моих операторов println, правильные значения возвращаются Node.compareTo (). Например, учитывая набор данных:

  • имя, частота
  • нужно, 3
  • кошка, 1
  • аккуратно, 2

Мой код выдает:
// добавить нужно
[Необходимость]
// добавить кота
кошка <нужно <br> [кошка, нужно]
// добавляем аккуратно
аккуратный> кот
[кошка, нужна, аккуратная]
когда значение PriorityQueue должно быть [cat, neat, need]
Любые подсказки относительно того, почему это происходит?

Ответы [ 2 ]

3 голосов
/ 29 марта 2011

Заказ от итератора для PriorityQueue не определен; порядок при вызове poll() должен соответствовать порядку компаратора. Из спецификации API,

iterator() Возвращает итератор для элементов в этой очереди. Итератор не вернуть элементы в любом конкретном заказ.

Если вам действительно нужен отсортированный набор, используйте SortedSet ИЛИ поместите вещи в коллекцию и используйте Collections.sort(). Однако, если вам действительно нужен pqueue, вот мой пример исправления: 

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

}

Дает: 

[need]
cat < need
[cat, need]
neat > cat
[cat, need, neat]
In order now:
neat < need
cat
neat
need
2 голосов
/ 29 марта 2011

PriorityQueues работают «вовремя».Если вы просто отобразите их содержимое, содержимое не будет в отсортированном порядке;они в куче (о которой, как вы уже упоминали, я думаю, вы бы знали об этом). В любом случае, чтобы упорядочить содержимое, вы должны извлекать элементы по одному за раз с помощью i poll ().

...