Кодирование Хаффмана

1function huffman(freqs: Array<[ch: string, n: number]>) {
2  // очередь с приоритетом: два самых редких сливаются в узел
3  const heap = freqs.map(([ch, n]) => ({ ch, n }))
4  while (heap.length > 1) {
5    heap.sort((a, b) => a.n - b.n)
6    const a = heap.shift()!
7    const b = heap.shift()!
8    heap.push({ ch: a.ch + b.ch, n: a.n + b.n })
9  }
10  return heap[0]! // корень дерева кодов
11}
12 
13function codes(node: Tree, prefix = ''): Record<string, string> {
14  if (node.ch.length === 1) return { [node.ch]: prefix || '0' }
15  return {
16    ...codes(node.left!, prefix + '0'),
17    ...codes(node.right!, prefix + '1'),
18  }
19}