Priority Queues with Huffman tree

i am trying to create a Huffman tree by reading in a file and counting the frequency of each letter space symbol etc. i'm using a Priorityqueue to queue the items from smallest to largest but when i insert them into the queue they dont queue correctly here is my code. package huffman;

import java.io.FileNotFoundException; import java.io.FileReader; import java.util.ArrayList; import java.util.PriorityQueue; import java.util.Scanner;

public class Huffman {

public ArrayList<Frequency> fileReader(String file)
{
    ArrayList<Frequency> al = new ArrayList<Frequency>();
    Scanner s;
    try {

        s = new Scanner(new FileReader(file)).useDelimiter("");
        while (s.hasNext())
        {
            boolean found = false;
            int i = 0;
            String temp = s.next();
            while(!found)
            {


                if(al.size() == i && !found)
                {
                    found = true;
                    al.add(new Frequency(temp, 1));
                }
                else if(temp.equals(al.get(i).getString()))
                {
                    int tempNum = al.get(i).getFreq() + 1;
     开发者_运维百科               al.get(i).setFreq(tempNum);
                    found = true;
                }
                i++;

            }



        }
    } catch (FileNotFoundException e) {
        // TODO Auto-generated catch block
        e.printStackTrace();
    }
    return al;
}
public void buildTree(ArrayList<Frequency> al)
{
    PriorityQueue<Frequency> pq = new PriorityQueue<Frequency>();
    for(int i = 0; i < al.size(); i++)
    {
        pq.add(al.get(i));          
    }
    while(pq.size() > 0)
    {
        System.out.println(pq.remove().getString());
    }
}
public void printFreq(ArrayList<Frequency> al)
{
    for(int i = 0; i < al.size(); i++)
    {
        System.out.println(al.get(i).getString() + "; " + al.get(i).getFreq());
    }
}

}

in the buildTree() method is where im having the problem. what im trying to do is queue Frequency objects which holds the letter/space/symbol and the frequency as an int the frequency class is this. public class Frequency implements Comparable { private String s; private int n;

Frequency(String s, int n)
{
    this.s = s;
    this.n = n;
}
public String getString()
{
    return s;
}
public int getFreq()
{
    return n;
}
public void setFreq(int n)
{
    this.n = n;
}
@Override
public int compareTo(Object arg0) {
    // TODO Auto-generated method stub
    return 0;
}

}

how can i get the priorityqueue to use the frequency number to queue them from smallest to biggest?

Actually you missed to implement the compareTo method to make your object effectively comparable.

The compareTo method, as documentation states, should

return a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

This means that in your case you should do something like:

public int compareTo(Object arg0)
{
  Frequency other = (Frequency)arg0;

  return n < other.n ? -1 : (n == other.n ? 0 : 1);
}

But mind that comparable has a generic type that is preferable: Comparable<T> so you can avoid the cast on arg0 to make it a Frequency object with static type safety too:

class Frequency implements Comparable<Frequency> {   
  public int compareTo(Frequency f2) {
    // directly compare
  }
}

I think that "Auto-generated method stub" needs to be filled in with a real implementation of a "compareTo" so as to satisfy the requirements for something to be Comparable, which I assume the PriorityQueue is going to rely upon. The implementation is probably going to be "n < arg0", with appropriate downcasting from Object.

A Priority Queue, just as a data structure, is based on the concept of an ordering - you use such a structure when you want to order elements in a certain way - which elements are more important than others, etc.

In Java, ordering objects is usually done in one of two ways - your objects implement the Comparable interface, or you supply a Comparator<E> which knows how to order objects of type E.

To determine which object is "more important" than another, the compareTo() method is invoked. This method has a pretty simple contract:

Compares this object with the specified object for order. Returns a negative integer, zero, or a positive integer as this object is less than, equal to, or greater than the specified object.

Your implementation of Frequency.compareTo() always returns 0 for the comparison. Thus, you are specifying that all Frequency objects are equal to any other Frequency objects. This is clearly not what you want.