java - java 将节点插入优先级队列

Question

嗨，我正在尝试将我创建的所有节点放入 pq 中，以便我可以根据权重对它们进行排序，然后删除前两项(最小的)，以便我可以构建一棵哈夫曼树，它是二叉树最好的方法是什么？谢谢

public class Main {

    public void main(String[] args) throws IOException {

        long start = System.currentTimeMillis();
        String inputFileName = args[0];
        FileReader reader = new FileReader(inputFileName);
        Scanner in = new Scanner(reader);

        // read in the data and do the work here
        // read a line at a time to enable newlines to be detected and allowed for

        while(in.hasNext()){
            CharacterMap<Character, Integer> hashMap = new CharacterMap<Character, Integer>();
            char[] chars = scanner.nextLine().toLowerCase().toCharArray();
            int c_count = 0;
            for (Character c : chars) {
                c_count += 1;
                if (hashMap.containsKey(c)) {
                    hashMap.put(c, hashMap.get(c) + 1);
                } else {
                    hashMap.put(c, 1);
                }
        }

            PriorityQueue<Node> pq = new PriorityQueue<Node>(new Comparator<Node>() {

            for (Map.Entry<Character, Integer> entry : hashMap.entrySet()){

                Node n = new Node();

                int f = entry.getValue();
                String c = entry.getKey();
                n.setWeight(f);
                n.setCharacter(c);

                n.setLeftChild(null);
                n.setRightChild(null);
                pq.add(n);
            }

        reader.close();

        String outputFileName = args[1];
        FileWriter writer = new FileWriter(outputFileName);
        writer.write("Input file " + inputFileName + "  Huffman algorithm\n\n");

        // write out the results here

        long end = System.currentTimeMillis();
        writer.write("\nElapsed time: " + (end - start) + " milliseconds");
        writer.close();
    }

}

Answer 1

如果你想获得优先级队列的Java实现来按权重对节点进行排序，你必须让你的节点类实现“comparable”接口(interface)。这意味着在节点类中放置一个“compareTo”方法并按权重定义比较，例如:

private static class Node implements Comparable<Node>{
    public int compareTo(Node n) {
        if(this.weight < n.weight){
            return -1;
        }else if(this.weight > n.weight){
            return 1;
        }else
            return 0;
    }
}