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) {
        //优先队列
        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);
        //广度优先遍历队列
        Queue<Node> bfsQueue = new LinkedList<Node>();
        //加入根结点
        bfsQueue.offer(root);
        //结果队列
        Queue<Node> results = new LinkedList<Node>();
        while(!bfsQueue.isEmpty()){
            Node current = bfsQueue.poll();
            Node leftChild = current.leftChild;
            Node rightChild = current.rightChild;
            //叶子结点为数据结点，加入结果队列
            if(leftChild== null && rightChild == null){
                results.offer(current);
            }
            //右结点权重大，if判断一定要在前
            if(rightChild != null){
                bfsQueue.offer(rightChild);
            }
            //左结点权重小，if判断一定要在后
            if(leftChild != null){
                bfsQueue.offer(leftChild);
            }
        }
        //测试结果
        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
         */

    }

    //构建哈夫曼树
    public static Node constuctHafumanTree(PriorityQueue<Node> pQueue){
        while(pQueue.size() > 1){
            Node left = pQueue.poll();//小权重结点在左
            Node right = pQueue.poll();//大权重结点在右
            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结点
        return pQueue.poll();
    }

    //拿到哈夫曼编码
    public static String getHafumanCode(Node node){
        //遍历是由底往上，比如001需要压栈最后取出转为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();
    }

}