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?

In case you have access to TreeNode code, You could add compareTo() method to it and implement Comparable interface. This could turn out to be easier for job you want to do. In this case your TreeNode contained elements should be always Comparables. — Lauri
– Lauri, Commented Oct 10, 2012 at 7:29
To provide better answer, it would be helpful to see implementation of TreeNode class. You could edit this question and add it here. — Lauri
– Lauri, Commented Oct 10, 2012 at 7:38

Luiggi Mendoza · Accepted Answer · 2012-10-10 07:32:30Z

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>>.

edited Oct 10, 2012 at 7:32

answered Oct 10, 2012 at 7:17

Luiggi Mendoza

85.9k16 gold badges160 silver badges354 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Lauri Over a year ago

In place of: "node1.compareTo(node2);" You should have "node1.getCharFreq().compareTo(node2.getCharFreq());" But that is assuming You have getCharFreq() method in TreeNode. You might have something more generic there, like getContent(), but it is needed to be able to access the inner element in TreeNode, otherwise You have to revrite TreeNode to be comparable.

Luiggi Mendoza Over a year ago

@Lauri right, answer edited. By the way, OP doesn't show how the data is stored in its TreeNode class, I'm assuming it could be a data property or similar.

Darkstarone Over a year ago

Alright, built the comparator, however, I'm not sure how to implement it. I've got: PriorityQueue<TreeNode<CharFreq>> pq = new PriorityQueue<TreeNode<CharFreq>>(trees.size(), comparator) but that yells at me for referencing non-static comparator in a static context.

Luiggi Mendoza Over a year ago

@Darkstarone did you create the Comparator inside the method, right? I've edited my answer to show you how to do it.

Darkstarone Over a year ago

Ahh, thank you very much. Makes a lot more sense now. First foray into priority Queues tonight. Thanks for making it easier!

mkhelif · Accepted Answer · 2012-10-10 07:11:16Z

0

The priority queue is using either a Comparator (provided in constructor) or it directly casts the object into Comparable.

To avoid the ClassCastException you should provide a Comparator of TreeNode. This way the queue will use the comparator instead of casting.

PriorityQueue<TreeNode<CharFreq>> pq = new PriorityQueue<TreeNode<CharFreq>>(initialCapacity, comparator);

answered Oct 10, 2012 at 7:11

mkhelif

1,55910 silver badges18 bronze badges

2 Comments

Darkstarone Over a year ago

The issue with creating a Comparator is that I'm unable to alter the TreeNode class due to assignment constraints!

Luiggi Mendoza Over a year ago

@Darkstarone you don't need to modify your TreeNode class to make a Comparator. Look at my answer to see a basic implementation.

Collectives™ on Stack Overflow

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

2 Answers 2

5 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related