import java.util.*;
/**
 * @author Jajing
 */
public class hafuman {

    private static class Node implements Comparable<Node>{
        Node parent;
        Node leftChild;
        Node rightChild;
        String data;
        int weight;
        Node(String data,int weight){
            this.data = data;
            this.weight =weight;
        }

        @Override
        public int compareTo(Node o) {
            //倒序
            return o.weight - this.weight;
        }
    }

    public static void main(String[] args) {
        //優(yōu)先隊(duì)列
        PriorityQueue<Node> pQueue = new PriorityQueue();
        pQueue.offer(new Node("A",20));
        pQueue.offer(new Node("B",15));
        pQueue.offer(new Node("C",10));
        pQueue.offer(new Node("D",5));
        pQueue.offer(new Node("E",1));
        Node root = constuctHafumanTree(pQueue);
        //廣度優(yōu)先遍歷隊(duì)列
        Queue<Node> bfsQueue = new LinkedList<Node>();
        //加入根結(jié)點(diǎn)
        bfsQueue.offer(root);
        //結(jié)果隊(duì)列
        Queue<Node> results = new LinkedList<Node>();
        while(!bfsQueue.isEmpty()){
            Node current = bfsQueue.poll();
            Node leftChild = current.leftChild;
            Node rightChild = current.rightChild;
            //葉子結(jié)點(diǎn)為數(shù)據(jù)結(jié)點(diǎn)，加入結(jié)果隊(duì)列
            if(leftChild== null && rightChild == null){
                results.offer(current);
            }
            //右結(jié)點(diǎn)權(quán)重大，if判斷一定要在前
            if(rightChild != null){
                bfsQueue.offer(rightChild);
            }
            //左結(jié)點(diǎn)權(quán)重小，if判斷一定要在后
            if(leftChild != null){
                bfsQueue.offer(leftChild);
            }
        }
        //測試結(jié)果
        List<String> list = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        for(Node node:results){
            String code = getHafumanCode(node);
            list.add(node.data+":"+code);
            sb.append(code);
        }
        System.out.println(sb.toString());
        for(String s:list){
            System.out.println(s);
        }
        /**
         * codeSTR: 10100100010000
         * E:1
         * D:01
         * C:001
         * B:0001
         * A:0000
         */

    }

    //構(gòu)建哈夫曼樹
    public static Node constuctHafumanTree(PriorityQueue<Node> pQueue){
        while(pQueue.size() > 1){
            Node left = pQueue.poll();//小權(quán)重結(jié)點(diǎn)在左
            Node right = pQueue.poll();//大權(quán)重結(jié)點(diǎn)在右
            Node parent = new Node("P",left.weight+right.weight);//往上冒
            parent.leftChild = left;
            parent.rightChild = right;
            left.parent = parent;
            right.parent = parent;
            pQueue.offer(parent);
        }
        //root結(jié)點(diǎn)
        return pQueue.poll();
    }

    //拿到哈夫曼編碼
    public static String getHafumanCode(Node node){
        //遍歷是由底往上，比如001需要壓棧最后取出轉(zhuǎn)為100
        Stack<Integer> codeStack = new Stack<Integer>();
        Node parent = node.parent;
        while(node != null && parent != null){
            if(node.parent.rightChild == node){
                codeStack.push(1);
            }else{
                codeStack.push(0);
            }
            node = parent;
            parent = node.parent;
        }
        StringBuilder sb = new StringBuilder();
        while(!codeStack.isEmpty()){
            sb.append(codeStack.pop());
        }
        return sb.toString();
    }

}