Huffman coding

Medium

Problem

Given characters and their frequencies, build an optimal prefix-free binary code: frequent characters get shorter codes, and no code is a prefix of another. Print each character's code, for example in preorder of the Huffman tree.

Example 1

Input:  chars = "abcdef", freq = [5, 9, 12, 13, 16, 45]
Output: f: 0, c: 100, d: 101, a: 1100, b: 1101, e: 111

Also asked as: Huffman Coding

Test cases

No automated tests for this problem yet. Use the examples above to check your output.

Your solution ✓ Solved

Ctrl/⌘ + Enter to run

This problem has no automated tests. Run executes your code and shows what it logs.

View solutionHide solution1 approach

1. Min-heap merge the two least-frequent nodes

Time O(n log n)Space O(n)

Repeatedly combine the two lowest-frequency subtrees into a parent whose frequency is their sum. The resulting tree gives prefix codes; left = 0, right = 1.

function huffman(freq) { // freq: { char: count }
let heap = Object.entries(freq).map(([ch, f]) => ({ ch, f, left: null, right: null }));
heap.sort((a, b) => a.f - b.f);
while (heap.length > 1) {
const a = heap.shift(), b = heap.shift();
const node = { ch: null, f: a.f + b.f, left: a, right: b };
let i = heap.findIndex((x) => x.f > node.f);
i === -1 ? heap.push(node) : heap.splice(i, 0, node);
}
const codes = {};
const walk = (n, code) => {
if (!n) return;
if (n.ch !== null) { codes[n.ch] = code || '0'; return; }
walk(n.left, code + '0');
walk(n.right, code + '1');
};
walk(heap[0], '');
return codes;
}