Published by Dimitris Kougioumtzis · Updated
Repeatedly merge the two least frequent trees, then use left/right paths as prefix-free binary codes.
Count symbol frequencies and repeatedly combine the two lightest trees. Assign 0 to a left edge and 1 to a right edge; leaf paths form a prefix-free code.
When to use Huffman prefix encoding
Teaching optimal binary prefix codes for a known symbol distribution.
Choosing an alternative
LZW adapts a dictionary of phrases while reading. This Huffman view first counts single-symbol frequencies and builds a static tree.
Worked example: input and state changes
Example input
mississippi
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Count symbols and initialize leaf frequencies.
State at this checkpoint
{ "values": [ 4, 1, 2, 4 ], "active": [], "kind": "graph", "directed": true, "chosen": [], "visited": [], "nodeLabels": [ "i", "m", "p", "s" ], "output": [], "result": 0 }Step 4: Encode m as 100.
State at this checkpoint
{ "values": [ 4, 1, 2, 4, 3, 7, 11 ], "active": [], "kind": "graph", "directed": true, "chosen": [], "visited": [], "nodeLabels": [ "i", "m", "p", "s", "merge", "merge", "merge" ], "output": [], "result": 0 }Step 8: Encode i as 11.
State at this checkpoint
{ "values": [ 4, 1, 2, 4, 3, 7, 11 ], "active": [], "kind": "graph", "directed": true, "chosen": [], "visited": [], "nodeLabels": [ "i", "m", "p", "s", "merge", "merge", "merge" ], "output": [], "result": 0 }Step 11: Encode i as 11.
State at this checkpoint
{ "values": [ 4, 1, 2, 4, 3, 7, 11 ], "active": [], "kind": "graph", "directed": true, "chosen": [], "visited": [], "nodeLabels": [ "i", "m", "p", "s", "merge", "merge", "merge" ], "output": [], "result": 0 }Step 15: Encoded 21 bits; frequency table travels with the stream.
State at this checkpoint
{ "values": [ 4, 1, 2, 4, 3, 7, 11 ], "active": [], "kind": "graph", "directed": true, "chosen": [], "visited": [], "nodeLabels": [ "i", "m", "p", "s", "merge", "merge", "merge" ], "output": [ 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 1, 0, 0, 2, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 21, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1 ], "result": 21 }
Expected final state
Encoded 21 bits; frequency table travels with the stream.
Complexity and input bounds
Family: Strings. Time complexity: O(n + alphabet^2) bounded tree scan.
Implementation detail: Inputs have at most sixteen lowercase letters. Ties choose the subtree with the smallest symbol; first child gets bit 0. One symbol uses code 0. Downloads write 26 frequencies, a bit count, and individual 0/1 payload entries, not a packed file. The bounded implementation scans active nodes instead of using a heap.
Space complexity: O(alphabet size) tree/code scratch storage plus output and saved visualization frames.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
1..16 lowercase letters; equal-frequency trees break ties by smallest symbol; a single symbol uses code 0.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Equal-frequency choices must be deterministic when a decoder rebuilds the tree. A single symbol needs an explicit nonempty code. Include frequency-table or codebook overhead when comparing file sizes.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // Lowercase ASCII integer codes, n 0..16. Deterministic Huffman tree: choose lowest frequency, then smallest symbol in subtree; first child gets bit 0. Single-symbol code is 0. Returns bit count; output capacity at least 91: [0..25] frequencies, [26] bit count, [27..] individual 0/1 bits (at most 64). Empty input writes 27 zeroes. No packed file framing; frequency-table overhead is not counted as compressed payload. O(n + alphabet^2) tree scans plus emitted bits, O(alphabet) scratch. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(text, n, output) { let freq = Array(256).fill(0); let code = Array(256).fill(0); let length = Array(256).fill(0); let node = 0; let count = 0; for (let i = 0; i < n; i++) { freq[text[i]-97]++; } for (let i = 0; i < 26; i++) { output[i] = freq[i]; } let left = Array(256).fill(0); let right = Array(256).fill(0); let parent = Array(256).fill(0); let smallest = Array(256).fill(0); let nodes = 26; let active = 0; let root = -1; let a = -1; let b = -1; for (let i = 0; i < 256; i++) { left[i] = -1; right[i] = -1; parent[i] = -1; smallest[i] = i; } for (let i = 0; i < 26; i++) { if (freq[i] > 0) { active++; root = i; } } while (active > 1) { a = -1; for (let k = 0; k < nodes; k++) { if (freq[k] > 0 && parent[k] == -1) { if (a == -1 || freq[k] < freq[a] || (freq[k] == freq[a] && smallest[k] < smallest[a])) { a = k; } } } parent[a] = nodes; b = -1; for (let k = 0; k < nodes; k++) { if (freq[k] > 0 && parent[k] == -1) { if (b == -1 || freq[k] < freq[b] || (freq[k] == freq[b] && smallest[k] < smallest[b])) { b = k; } } } parent[b] = nodes; left[nodes] = a; right[nodes] = b; freq[nodes] = freq[a]+freq[b]; smallest[nodes] = smallest[a]; if (smallest[b] < smallest[nodes]) { smallest[nodes] = smallest[b]; } root = nodes; nodes++; active--; } if (root == -1) { output[26] = 0; return 0; } for (let c = 0; c < 26; c++) { if (freq[c] > 0) { node = c; while (parent[node] != -1) { if (right[parent[node]] == node) { code[c] = code[c] | (1 << length[c]); } length[c]++; node = parent[node]; } if (length[c] == 0) { length[c] = 1; } } } for (let i = 0; i < n; i++) { for (let k = length[text[i]-97]-1; k >= 0; k--) { output[27+count] = (code[text[i]-97] >> k) & 1; count++; } } output[26] = count; return count; } |
Source
Original Huffman research for minimum-redundancy prefix coding. The teaching implementation adds a deterministic tie convention, bounded lowercase alphabet and explicit single-symbol bit convention.
- A Method for the Construction of Minimum-Redundancy Codes
David A. Huffman (1952). Original research paper.