import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Comparator;

public class Node
{
    private Node left;
    private Node right;
    private int anzahl;
    private Character buchstabe;

    public Node()
    {
    }

    public Node(Node left, Node right)
    {
        this.left = left;
        this.right = right;
    }

    public Node getLeft(){return left;}

    public void setLeft(Node left){this.left = left;}

    public Node getRight(){return right;}

    public void setRight(Node right){this.right = right;}

    public int getAnzahl(){return anzahl;}

    public void setAnzahl(int anzahl){this.anzahl = anzahl;}

    public Character getBuchstabe(){return buchstabe;}

    public void setBuchstabe(Character buchstabe){this.buchstabe = buchstabe;}

    public static Node erstellen(Map<Character, Integer> häufigkeiten)
    {
        PriorityQueue<Node> nodes = new PriorityQueue<Node>(Comparator.comparingInt(n -> n.anzahl));

        for (var entry : häufigkeiten.entrySet()) 
        {
            Node node = new Node();
            node.setAnzahl(entry.getValue());
            node.setBuchstabe(entry.getKey());
            nodes.add(node);
        }

        while (nodes.size() > 1)
        {
            Node min1 = nodes.poll();
            Node min2 = nodes.poll();
            Node wurzel = new Node();
            wurzel.setLeft(min1);
            wurzel.setRight(min2);
            wurzel.setAnzahl(min1.getAnzahl() + min2.getAnzahl());
            nodes.add(wurzel);
        }
        return nodes.poll();
    }
}