对于一组给定的叶子结点，他们的权值集合为w=｛4,2,1,7,3｝，给出由此集合构造哈夫曼树的过程

Question

对于一组给定的叶子结点，他们的权值集合为w=｛4,2,1,7,3｝，给出由此集合构造哈夫曼树的过程

Answer 1

import java.util.PriorityQueue;

public class HuffmanTree {
    private static class Node implements Comparable<Node> {
        int value;
        Node left;
        Node right;

        Node(int value) {
            this.value = value;
        }

        @Override
        public int compareTo(Node o) {
            return this.value - o.value;
        }
    }

    public static Node buildHuffmanTree(int[] w) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        for (int weight : w) {
            queue.offer(new Node(weight));
        }

        while (queue.size() > 1) {
            Node left = queue.poll();
            Node right = queue.poll();
            Node parent = new Node(left.value + right.value);
            parent.left = left;
            parent.right = right;
            queue.offer(parent);
        }
        return queue.poll();
    }
}