Huffman prefix encoding: Examples & Code

Algorithm Visualizations November 16, 2026 javascript

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.

Open the 3D visualization

Huffman prefix encoding example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

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.

  1. 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
    }
  2. 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
    }
  3. 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
    }
  4. 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
    }
  5. 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:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 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.