Huffman Encoding

# Huffman Encoding ## Difficulty Medium ## Tags `tree`, `greedy`, `heap` ## Problem Statement Given a set of characters and their frequencies, implement Huffman Coding to generate optimal prefix codes for each character. A prefix code means no code is a prefix of another (e.g., if "01" is a code, "010" cannot be). ## Constraints - Input is a dictionary mapping characters to their integer frequencies. - All frequencies are positive integers. - Return a dictionary mapping characters to their binary string codes. ## Signatures ### Python ```python def huffman_codes(frequencies: Dict[str) -> Dict[str, str]: pass ``` ### Java ```java public class Solution { public Object huffman_codes(Object frequencies) { return null; } } ``` ### Csharp ```csharp public class Solution { public Object huffman_codes(Object frequencies) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: Object huffman_codes(Object frequencies) { } }; ``` ### C ```c Object huffman_codes(Object frequencies) { } ``` ### Ruby ```ruby def huffman_codes(frequencies) end ``` ### Perl ```perl sub huffman_codes { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def huffman_codes(frequencies: Object): Object = { } } ``` ### Haskell ```haskell huffman_codes :: ... -> ... huffman_codes args = undefined ``` ### Clojure ```clojure (defn huffman_codes [frequencies] ) ``` ### Scheme ```scheme (define (huffman_codes frequencies) ) ``` ## Examples ### Example 1 **Input:** ``` frequencies = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45} ``` **Output:** ``` {'f': '0', 'c': '100', 'd': '101', 'a': '1100', 'b': '1101', 'e': '111'} ``` **Explanation:** Higher frequency characters get shorter codes. 'f' (45) gets the shortest code "0". ### Example 2 **Input:** ``` frequencies = {'a': 1, 'b': 1} ``` **Output:** ``` {'a': '0', 'b': '1'} # or {'a': '1', 'b': '0'} ``` ### Example 3 **Input:** ``` frequencies = {'x': 10} ``` **Output:** ``` {'x': '0'} # Single character gets code '0' or '1' ``` ## Hints 1. Use a min-heap (priority queue) based on frequency. 2. Create a leaf node for each character. 3. While heap has more than one node: - Extract two nodes with smallest frequencies. - Create a new internal node with these as children, frequency = sum. - Insert new node back into heap. 4. The remaining node is the root. Traverse tree to assign codes (left=0, right=1).