Huffman Coding
GreedyHardConstruct optimal prefix codes for data compression.
Alt+Shift+H
Configuration Panel
Huffman Tree and Prefix Codes
Double-click empty canvas to create root, select node to add child or delete.
Time Complexity
O(N log N) with priority queue
Space Complexity
O(N) tree size nodes buffers
Conceptual Overview
Huffman Coding is an entropy encoding algorithm used for lossless data compression, assigning variable-length prefix codes based on character frequencies.
Greedy Choice Property
Repeatedly merge the two nodes with the lowest frequencies into a parent node whose frequency is the sum of the children's frequencies.
Optimal Substructure
An optimal Huffman tree for N characters contains an optimal Huffman tree for N-1 characters as a subtree, merged via the lowest frequency pair.
Proof Idea / Correction
Proof by sibling property: if the lowest frequency characters are not leaves at the bottom of the tree, swapping them with higher frequency nodes increases the total weighted path length.
Source: CP-Algorithms greedy reference