Priority Queue ordering in Java issue

Question

I want to make a priority queue of nodes, wherein priority of nodes is their frequencies. But the output doesn't contain the first element in the right position, rest all are in correct positons.

    import java.util.*;
class node implements Comparable<node>{
        char key;
        int freq;
        node(){}
        node(char k,int f){
                key=k;
                freq=f;
        }
    public int compareTo(node n){
            if(freq>n.freq)return 1;
            return 0;
        }
}

public class test{
    public static void main(String[] args){
        node x=new node('x',4);
        node a=new node('a',2);
        node b=new node('b',1);
        node c=new node('c',7);
        PriorityQueue<node> q = new PriorityQueue<node>();

        q.offer(a);
        q.offer(b);
        q.offer(c);
        q.offer(x);

        while(!q.isEmpty()){
            node d=q.poll();
            System.out.println(d.key+" "+d.freq);
        }
    }
}

Output:

Should not the ordering be b , a, x, c Thanks.

JB Nizet · Accepted Answer · 2012-09-06 12:33:53Z

5

Your comparator is wrong: if freq < n.freq, it returns 0 instead of returning a negative number.

The code should be

return Ints.compare(freq, n.freq); // with Guava

or

return Integer.valueOf(freq).compareTo(Integer.valueOf(n.freq)) // with plain Java

or

if (freq > n.freq) return 1;
if (freq < n.freq) return -1;
return 0;

edited Sep 6, 2012 at 12:33

answered Sep 6, 2012 at 12:25

JB Nizet

694k94 gold badges1.3k silver badges1.3k bronze badges

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

2 Comments

Jignesh Over a year ago

then what is the need of returning o?

JB Nizet Over a year ago

0 is returned when objects are considered equal, i.e. when the frequencies are the same.

Vartlok · Accepted Answer · 2012-09-06 12:24:45Z

2

Add
else if (freq<n.freq) return -1;
into public int compareTo(node n)

answered Sep 6, 2012 at 12:24

Vartlok

2,5993 gold badges34 silver badges47 bronze badges

Collectives™ on Stack Overflow

Priority Queue ordering in Java issue

2 Answers 2

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related