哈夫曼編碼與哈夫曼樹的 java實作

有關哈夫曼樹的介紹，請參考這篇部落格【算法總結】哈夫曼樹和哈夫曼編碼，具體實作代碼如下：

import java.util.PriorityQueue;

public class HuffmanCoding {

    public static void main(String[] args){
        int[] nums = {35,25,15,15,10};
        String[] arr = {"A","B","C","D","E"};
        huffmanCoding(nums,arr);
        System.out.println(huffmanCoding(nums));
    }

    /**
     * 給定待編碼字元串數組和出現的頻率，建構哈夫曼樹，并列印輸出哈夫曼編碼（注意哈夫曼編碼不唯一）
     * @param nums 待編碼字元串出現的頻率
     * @param arr 待編碼字元串數組
     */
    public static void huffmanCoding(int[] nums,String[] arr){
        HuffmanNode[] nodes = new HuffmanNode[nums.length];
        PriorityQueue<HuffmanNode> queue = new PriorityQueue<>();
        for(int i = 0;i < nums.length;i ++){
            HuffmanNode node = new HuffmanNode(nums[i],arr[i]);
            nodes[i] = node;
            queue.add(node);
        }
        while(queue.size() > 1){
            HuffmanNode left = queue.poll();//預設左節點頻率小于右節點頻率
            HuffmanNode right = queue.poll();
            HuffmanNode parent = new HuffmanNode(left.frequency + right.frequency,null);
            parent.left = left;
            parent.right = right;
            left.parent = parent;
            left.isleft = true;
            right.parent = parent;
            right.isleft = false;
            queue.add(parent);
        }
        for(int i = 0;i < nodes.length;i ++){
            HuffmanNode node = nodes[i];
            System.out.print(node.value + "   ");
            while(node != null && node.parent != null){
                if(node.isleft)
                    System.out.print(0);
                else
                    System.out.print(1);
                node = node.parent;
            }
            System.out.println();
        }
    }

    /**
     * 給定待編碼字元出現的頻率，輸出所建構出的哈夫曼樹的帶權路徑長度
     * @param nums 待編碼字元串出現的頻率
     */
    public static long huffmanCoding(int[] nums){
        long res = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i = 0;i < nums.length;i ++){
            queue.add(nums[i]);
        }
        while(queue.size() > 1){
            int temp = queue.poll() + queue.poll();
            res += temp;
            queue.add(temp);
        }
        return res;
    }
}

class HuffmanNode implements Comparable<HuffmanNode>{
    int frequency;
    String value;
    boolean isleft;//标記節點是否是左節點
    HuffmanNode parent;
    HuffmanNode left;
    HuffmanNode right;
    public HuffmanNode(int frequency,String value){
        this.frequency = frequency;
        this.value = value;
        this.left = null;
        this.right = null;
        this.parent = null;
    }
    @Override
    public int compareTo(HuffmanNode o) {
        if(this.frequency < o.frequency)
            return -1;
        else if(this.frequency > o.frequency)
            return 1;
        else
            return 0;
    }
}