Using a priority queue on a non-comparable object with a comparable object inside it

Question

I'm building a huffman tree for a class currently. After reviewing my available options I decided to go the priority queue method. However, when I try to run the below code I get a ClassCastException on TreeNode (on the first pq.offer line).

public static TreeNode<CharFreq> buildTree(ArrayList<TreeNode<CharFreq>> trees) throws IOException {

   PriorityQueue<TreeNode<CharFreq>> pq = new PriorityQueue<TreeNode<CharFreq>>();

   for (int i = 0; i < trees.size(); i++) {
     if (trees.get(i).getItem().getFreq() > 0) {
       pq.offer(new TreeNode<CharFreq>(new CharFreq(trees.get(i).getItem().getChar(), trees.get(i).getItem().getFreq())));
     }
   }  

   while (pq.size() > 1) {    
       TreeNode<CharFreq> leftNode = pq.poll();
       TreeNode<CharFreq> rightNode = pq.poll();
       TreeNode<CharFreq> parentNode = new TreeNode<CharFreq>(new CharFreq('\u0000', ((leftNode.getItem().getFreq()) + (rightNode.getItem().getFreq()))), leftNode, rightNode);
   }  

   return pq.poll();

}

I know it's not a comparable class, however, CharFreq is, and my question is am I able to fix my code so it avoids this casting problem?

Answer 1

You can create a custom comparator: Comparator<TreeNode<CharFreq>> and use it when creating the PriorityQueue:

http://docs.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html#PriorityQueue(int, java.util.Comparator)

Creates a PriorityQueue with the specified initial capacity that orders its elements according to the specified comparator

Using the anonymous class concept, you can have a code like this:

public static TreeNode<CharFreq> buildTree(ArrayList<TreeNode<CharFreq>> trees)
    throws IOException {
    Comparator<TreeNode<CharFreq>> comparator = new Comparator<TreeNode<CharFreq>>() {

        //basic implementation, you must use your own!
        public int compare(TreeNode<CharFreq> node1, TreeNode<CharFreq> node2) {
            return node1.data.compareTo(node2.data);
        }
    };
    PriorityQueue<TreeNode<CharFreq>> pq = new PriorityQueue<TreeNode<CharFreq>>(10, comparator);
    //the rest of your code...
}

Note that using this way means that you have to create a custom Comparator<TreeNode<YourClass>> everytime you need to create a PriorityQueue<TreeNode<YourClass>>.