Objects added to a PriorityQueue are not ordered by their priority

Question

I'm trying to implement a heap using a PriorityQueue as follows:

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

Where I've defined Node as as private class inside the same class that holds the above method. Node is defined as:

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

However, when I add nodes to the PriorityQueue, they are not ordered by frequency. Based on output from my println statements, the correct values are returned by Node.compareTo(). For example, given the dataset:

• name, frequency
• need, 3
• cat, 1
• neat, 2

My code produces:
// add need
[need]
// add cat
cat < need
[cat, need]
// add neat
neat > cat
[cat, need, neat]
when the PriorityQueue should be [cat, neat, need]
Any tips as to why this is happening?

Answer 1

The order from an iterator for PriorityQueue is undefined; the order when calling poll() should be the comparator ordering. From the API spec,

iterator() Returns an iterator over the elements in this queue. The iterator does not return the elements in any particular order.

If what you really need is a sorted set, use SortedSet OR put things into a collection and use Collections.sort(). If, however, you really need a pqueue, here's my example fix:

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

}

Gives:

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

Answer 2

PriorityQueues work on a "just in time" basis. If you just display their contents, the contents are not going to be in sorted order; they're in a heap (which, since you mentioned, I think you'd know about.) Anyway, to get the contents in order, you have to pull the items off one at a time with i poll().