Building a Huffman tree

Question

I've been working on this Huffman tree builder:

// variable al is an array list that holds all the different characters and their frequencies
// variable r is a Frequency which is supposed to be the roots for all the leaves which holds a null string and the frequencies of the combined nodes removed from the priority queue
public Frequency buildTree(ArrayList<Frequency> al)
{
    Frequency r = al.get(0);
    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());
    }*/

    for(int i = 0; i < al.size() - 1; i++)
    {   
       Frequency p = pq.remove(); 
       Frequency q = pq.remove();
       int temp = p.getFreq() + q.getFreq();
       r = new Frequency(null, temp);
       r.left = p; 
       r.right = q;
       pq.add(r);  // put in the correct place in the priority queue
    }
    pq.remove(); // leave the priority queue empty
    return(r); // this is the root of the tree built

}

what the code is trying to do english is

add all the characters with their frequencies to a priority queue from lowest frequency to greatest. next for the size of the ArrayList al (which contains all the characters) dequeue the first two then set a new root to have a left and right child that are the 2 nodes dequeued then insert the new root with the combined frequencies of the 2 dequeued items into the priority queue. thats all the method should do.

This method is supposed to build the Huffman tree, but it is building it incorrectly I've followed the code and built the tree by hand but what I get on paper is different from what the program is! The correct answer as generated by a different program is not the same as my solution. The input data (letters and frequencies) are:

a 6
b 5
space 5
c 4
d 3
e 2
f 1

as for the text that im reading from it doesn't matter because the frequencies are already right here. all i need 2 do is build the tree from these frequencies.

Answer 1

when is this due? I would start writing unit tests for each functional bit of your implementation -- you might be able to expose your problem that way. Also fix your formatting for this mess

"public Frequency buildTree(ArrayList al) { Frequency r = al.get(1); PriorityQueue pq = new PriorityQueue(); for(int i = 0; i < al.size(); i++) { pq.add(al.get(i)); } /while(pq.size() > 0) { System.out.println(pq.remove().getString()); }/"

edit- after formatting -- Im having a hard time reading your code. Make variable names descriptive. 'r' doesn't tell me anything, and neither does 'al'. It would help to know what the text your are encoding is....

Answer 2

Can you try to write out your algorithm in plain language, ignoring any Java details? This might help you understand where something is going wrong (either in the algorithm or in the code implementing it), but also help people help you out.

Regardless of the algorithm, do you really intend for your root node to start with the second element in the ArrayList? Lists are indexed starting at 0, not 1. List.get(1) returns the second element.

public Frequency buildTree(ArrayList<Frequency> al) {
    Frequency r = al.get(1);