HuffmanCoding.java

import java.util.*;

class HuffmanNode {
    char character;
    int frequency;
    HuffmanNode left;
    HuffmanNode right;

    HuffmanNode(char character, int frequency) {
        this.character = character;
        this.frequency = frequency;
    }
}

class HuffmanComparator implements Comparator<HuffmanNode> {
    public int compare(HuffmanNode x, HuffmanNode y) {
        return x.frequency - y.frequency;
    }
}

public class HuffmanCoding {

    static Map<Character, String> huffmanCodes;

    private static void generateCodes(HuffmanNode root, String code) {
        if (root == null)
            return;

        if (root.left == null && root.right == null) {
            huffmanCodes.put(root.character, code);
        }

        generateCodes(root.left, code + "0");
        generateCodes(root.right, code + "1");
    }

    private static HuffmanNode buildTree(String text) {
        int[] freq = new int[256];

        for (char c : text.toCharArray()) {
            freq[c]++;
        }

        PriorityQueue<HuffmanNode> pq = new PriorityQueue<>(new HuffmanComparator());

        for (int i = 0; i < 256; i++) {
            if (freq[i] > 0) {
                pq.add(new HuffmanNode((char) i, freq[i]));
            }
        }

        while (pq.size() > 1) {
            HuffmanNode left = pq.poll();
            HuffmanNode right = pq.poll();

            HuffmanNode parent = new HuffmanNode('-', left.frequency + right.frequency);

            parent.left = left;
            parent.right = right;

            pq.add(parent);
        }

        return pq.poll();
    }

    private static String encode(String text) {
        StringBuilder encoded = new StringBuilder();
        for (char c : text.toCharArray()) {
            encoded.append(huffmanCodes.get(c));
        }
        return encoded.toString();
    }

    // ✅ Web-friendly method
    public static String encodeText(String text) {
        huffmanCodes = new HashMap<>();

        HuffmanNode root = buildTree(text);
        generateCodes(root, "");

        return encode(text);
    }
}