1

我想制作一个节点的优先级队列，其中节点的优先级是它们的频率。但是输出不包含正确位置的第一个元素，其余的都在正确的位置。

    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);
        }
    }
}

输出：

    a 2
    b 1
    x 4
    c 7

不应该是 b , a, x, c 谢谢。

4

2 回答 2

5

您的比较器是错误的： if freq < n.freq，它返回 0 而不是返回负数。

代码应该是

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

或者

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

或者

if (freq > n.freq) return 1;
if (freq < n.freq) return -1;
return 0;
于 2012-09-06T12:25:44.050 回答
2

添加
else if (freq<n.freq) return -1;
到 public int compareTo(node n)

于 2012-09-06T12:24:45.750 回答