Implementation

  // Node represents a node in the Huffman tree
static class Node implements Comparable<Node> {
    char symbol; // The character (symbol) stored in this node; '\0' for internal nodes
    int freq; // Frequency (weight) of this node/subtree
    Node left; // Pointer to left child (represents '0' bit)
    Node right; // Pointer to right child (represents '1' bit)

    // Constructor for leaf nodes
    Node(char symbol, int freq) {
        this.symbol = symbol;
        this.freq = freq;
        this.left = this.right = null;
    }

    // Constructor for internal nodes: merge two subtrees
    Node(Node left, Node right) {
        this.symbol = '\0';
        this.freq = left.freq + right.freq;
        this.left = left;
        this.right = right;
    }

    // Compare Nodes
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.freq, other.freq);
    }
}
  

  static class Node implements Comparable<Node> {
    // Compare Nodes
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.freq, other.freq);
    }
}
  

  public static Node buildHuffmanTree(String data) {
    // 1) Count character frequencies
    Map<Character, Integer> freq = new HashMap<>();
    for (char ch : data.toCharArray()) {
        freq.put(ch, freq.getOrDefault(ch, 0) + 1);
    }

    // 2) Initialize a min-heap of one-node trees
    PriorityQueue<Node> pq = new PriorityQueue<>();
    for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
        pq.add(new Node(entry.getKey(), entry.getValue()));
    }

    // 3) Merge until one tree remains
    while (pq.size() > 1) {
        // Extract two nodes with smallest frequencies
        Node left = pq.poll();
        Node right = pq.poll();

        // Create a new parent node with combined frequency
        pq.add(new Node(left, right));
    }

    // The remaining node is the root of the Huffman tree
    return pq.poll();
}
  

  public static void generateCodes(Node node, String prefix, Map<Character, String> codeboo) {
if (node == null) return;

    if (node.symbol != '\0') {
        // If this is a leaf node, assign the code (use "0" if only one symbol)
        codebook.put(node.symbol, prefix.isEmpty() ? "0" : prefix);
    } else {
        // Internal: go left (add '0') and right (add '1')
        generateCodes(node.left, prefix + '0', codebook);
        generateCodes(node.right, prefix + '1', codebook);
    }
}
  

  public static void main(String[] args) {
    System.setOut(new PrintStream(System.out, true, StandardCharsets.UTF_8));

    // Example input string to encode
    String text = "AAABBBBBAAABBDDCCCCCDDDDBBAAAAAAAAAAACCCCAAAEEEEAAADDDAADAAAABBAADDACCACAAAAEEEBBEEAAAADDDDAA";

    // Build Huffman tree based on character frequencies
    Node root = buildHuffmanTree(text);

    // Generate the codebook (mapping from char to codeword)
    Map<Character, String> codes = new HashMap<>();
    generateCodes(root, "", codes);

    // Output the resulting Huffman codes
    System.out.println("Codewords:");
    for (Map.Entry<Character, String> entry : codes.entrySet()) {
        System.out.println("'" + entry.getKey() + "': " + entry.getValue());
    }
}