1
class HuffmanNode {
2
  char: string | null;      //Non-null indicates a leaf node
3
  freq: number;             //Node weight (sum of frequencies)
4
  left: HuffmanNode | null;
5
  right: HuffmanNode | null;
6

7
  constructor(
8
    char: string | null,
9
    freq: number,
10
    left: HuffmanNode | null = null,
11
    right: HuffmanNode | null = null
12
  ) {
13
    this.char = char;
14
    this.freq = freq;
15
    this.left = left;
16
    this.right = right;
17
  }
18

19
  /** Check whether it is a leaf node */
20
  isLeaf(): boolean {
21
    return this.char !== null;
22
  }
23
}

1
class MinHeap {
2
  private heap: HuffmanNode[] = [];
3

4
  size(): number {
5
    return this.heap.length;
6
  }
7

8
  push(node: HuffmanNode): void {
9
    this.heap.push(node);
10
    this.bubbleUp(this.heap.length - 1);
11
  }
12

13
  pop(): HuffmanNode {
14
    if (this.size() === 1) return this.heap.pop()!;
15
    const top = this.heap[0];
16
    this.heap[0] = this.heap.pop()!;
17
    this.bubbleDown(0);
18
    return top;
19
  }
20

21
  private swap(i: number, j: number): void {
22
    [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
23
  }
24

25
  private bubbleUp(idx: number): void {
26
    while (idx > 0) {
27
      const parent = Math.floor((idx - 1) / 2);
28
      if (this.heap[idx].freq >= this.heap[parent].freq) break;
29
      this.swap(idx, parent);
30
      idx = parent;
31
    }
32
  }
33

34
  private bubbleDown(idx: number): void {
35
    while (true) {
36
      const left = idx * 2 + 1;
37
      const right = idx * 2 + 2;
38
      let smallest = idx;
39

40
      if (left < this.size() && this.heap[left].freq < this.heap[smallest].freq)
41
        smallest = left;
42
      if (right < this.size() && this.heap[right].freq < this.heap[smallest].freq)
43
        smallest = right;
44
      if (smallest === idx) break;
45

46
      this.swap(idx, smallest);
47
      idx = smallest;
48
    }
49
  }
50
}

1
function buildHuffmanTree(freqMap: Map<string, number>): HuffmanNode {
2
  const heap = new MinHeap();
3

4
  //Add all character nodes to the min-heap
5
  for (const [char, freq] of freqMap) {
6
    heap.push(new HuffmanNode(char, freq));
7
  }
8

9
  //Greedily merge until only one root node remains
10
  while (heap.size() > 1) {
11
    const left = heap.pop();   //Smallest
12
    const right = heap.pop();  //Second smallest
13
    const merged = new HuffmanNode(
14
      null,
15
      left.freq + right.freq,
16
      left,
17
      right
18
    );
19
    heap.push(merged);
20
  }
21

22
  return heap.pop();
23
}

1
function generateCodes(root: HuffmanNode): Map<string, string> {
2
  const codes = new Map<string, string>();
3

4
  function dfs(node: HuffmanNode, path: string): void {
5
    if (node.isLeaf()) {
6
      //For single-character input, set the code to "0" (otherwise path is an empty string)
7
      codes.set(node.char!, path || '0');
8
      return;
9
    }
10
    if (node.left) dfs(node.left, path + '0');
11
    if (node.right) dfs(node.right, path + '1');
12
  }
13

14
  dfs(root, '');
15
  return codes;
16
}

1
function encode(text: string, codes: Map<string, string>): string {
2
  let result = '';
3
  for (const ch of text) {
4
    const code = codes.get(ch);
5
    if (code === undefined) {
6
      throw new Error(`Character '${ch}' is not in the encoding table`);
7
    }
8
    result += code;
9
  }
10
  return result;
11
}
12

13
function decode(bits: string, root: HuffmanNode): string {
14
  let result = '';
15
  let node = root;
16

17
  for (const bit of bits) {
18
    node = bit === '0' ? node.left! : node.right!;
19

20
    if (node.isLeaf()) {
21
      result += node.char;
22
      node = root; //Return to the root node and continue decoding the next character
23
    }
24
  }
25

26
  if (node !== root) {
27
    throw new Error('Decoding failed: incomplete encoded sequence');
28
  }
29

30
  return result;
31
}

1
//===== Test =====
2
const text = "ABRACADABRA";
3

4
//1. Count frequencies
5
const freqMap = new Map<string, number>();
6
for (const ch of text) {
7
  freqMap.set(ch, (freqMap.get(ch) || 0) + 1);
8
}
9
console.log('Frequency table:', freqMap);
10
// Map { 'A' => 5, 'B' => 2, 'R' => 2, 'C' => 1, 'D' => 1 }
11

12
//2. Build the Huffman tree
13
const root = buildHuffmanTree(freqMap);
14

15
//3. Generate the code table
16
const codes = generateCodes(root);
17
console.log('Encoding table:', codes);
18
// Map { 'A' => '0', 'B' => '10', 'R' => '11', 'C' => '100', 'D' => '101' }
19

20
//4. Encode
21
const encoded = encode(text, codes);
22
console.log('Encoding result:', encoded);
23
console.log('Encoding length:', encoded.length, 'bits');
24
//Encoded result: 010110010011001011010
25
//Encoded length: 21 bits
26
//Original ASCII: 11 × 8 = 88 bits → compressed to 23.9%
27

28
//5. Decode and verify
29
const decoded = decode(encoded, root);
30
console.log('Decoding result:', decoded);
31
console.log('Verification passed:', decoded === text);
32
//Decoded result: ABRACADABRA
33
//Verification passed: true