Huffman Coding using Greedy Technique
Problem Statement
Given a set of characters and their frequencies, generate prefix-free binary codes using Huffman Coding such that the total cost of encoding is minimized.
Technique Used
Greedy Algorithm
Data Structures Used
- Min Heap (Priority Queue)
- Binary Tree
Algorithm
- Read the number of characters
n. - Read the frequencies of all characters.
- Create a leaf node for each frequency and insert it into a min heap.
- While more than one node exists in the heap:
- Remove the two nodes with the smallest frequencies.
- Create a new internal node with frequency equal to their sum.
- Insert the new node back into the heap.
- Traverse the Huffman tree:
- Left child →
0 - Right child →
1
- Left child →
- Print the Huffman codes at each leaf node.
Properties of Huffman Coding
- Huffman codes are prefix-free.
- Characters with higher frequencies get shorter codes.
- Ensures optimal data compression.
Time and Space Complexity
- Time Complexity:
O(n log n) - Space Complexity:
O(n)
Output
Displays the generated Huffman codes for the given frequencies.