Huffman coding
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.
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;}