Huffman Encoding in DSA Javascript

Mental Model

Huffman encoding builds a tree to assign shorter codes to frequent letters and longer codes to rare ones, saving space.

Analogy: Imagine packing a suitcase: you put small, frequent items in easy-to-reach spots and big, rare items in harder spots to save space efficiently.

Characters with frequencies:
a:5  b:9  c:12  d:13  e:16  f:45

Initial nodes:
[a:5]  [b:9]  [c:12]  [d:13]  [e:16]  [f:45]

Dry Run Walkthrough

Input: characters with frequencies: a:5, b:9, c:12, d:13, e:16, f:45

Goal: Build Huffman tree and assign binary codes to each character minimizing total bits

Step 1: Pick two smallest frequencies a:5 and b:9, merge into node ab:14

[ab:14]  [c:12]  [d:13]  [e:16]  [f:45]

Why: Combine smallest to build tree bottom-up, ensuring frequent chars get shorter codes

Step 2: Pick two smallest c:12 and d:13, merge into node cd:25

[ab:14]  [cd:25]  [e:16]  [f:45]

Why: Continue merging smallest nodes to build tree

Step 3: Pick two smallest ab:14 and e:16, merge into node abe:30

[cd:25]  [abe:30]  [f:45]

Why: Merge next smallest nodes to build higher tree levels

Step 4: Pick two smallest cd:25 and abe:30, merge into node abcde:55

[abcde:55]  [f:45]

Why: Merge to approach root node

Step 5: Merge last two nodes abcde:55 and f:45 into root:100

[root:100]

Why: Final merge completes Huffman tree

Step 6: Assign binary codes by traversing tree: left edge=0, right edge=1

f: 0
a: 1100
b: 1101
c: 100
d: 101
e: 111

Why: Codes assigned so frequent chars have shorter codes

Result:

Huffman codes:
f:0
a:1100
b:1101
c:100
d:101
e:111

Annotated Code

DSA Javascript

class Node {
  constructor(char, freq, left = null, right = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

class MinHeap {
  constructor() {
    this.heap = [];
  }

  insert(node) {
    this.heap.push(node);
    this.bubbleUp();
  }

  bubbleUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      let parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex].freq <= this.heap[index].freq) break;
      [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
      index = parentIndex;
    }
  }

  extractMin() {
    if (this.heap.length === 1) return this.heap.pop();
    const min = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.bubbleDown();
    return min;
  }

  bubbleDown() {
    let index = 0;
    const length = this.heap.length;
    while (true) {
      let left = 2 * index + 1;
      let right = 2 * index + 2;
      let smallest = index;

      if (left < length && this.heap[left].freq < this.heap[smallest].freq) smallest = left;
      if (right < length && this.heap[right].freq < this.heap[smallest].freq) smallest = right;
      if (smallest === index) break;
      [this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
      index = smallest;
    }
  }

  size() {
    return this.heap.length;
  }
}

function buildHuffmanTree(freqMap) {
  const heap = new MinHeap();
  for (const [char, freq] of Object.entries(freqMap)) {
    heap.insert(new Node(char, freq));
  }

  while (heap.size() > 1) {
    const left = heap.extractMin(); // extract smallest freq node
    const right = heap.extractMin(); // extract next smallest
    const merged = new Node(null, left.freq + right.freq, left, right); // merge nodes
    heap.insert(merged); // insert merged node back
  }

  return heap.extractMin(); // root of Huffman tree
}

function generateCodes(node, prefix = '', codes = {}) {
  if (!node) return;
  if (node.char !== null) {
    codes[node.char] = prefix; // assign code to character
  }
  generateCodes(node.left, prefix + '0', codes); // left edge is 0
  generateCodes(node.right, prefix + '1', codes); // right edge is 1
  return codes;
}

// Driver code
const freqMap = { a: 5, b: 9, c: 12, d: 13, e: 16, f: 45 };
const root = buildHuffmanTree(freqMap);
const codes = generateCodes(root);
for (const char of Object.keys(freqMap)) {
  console.log(`${char}: ${codes[char]}`);
}

const left = heap.extractMin(); // extract smallest freq node

extract smallest frequency node to merge

const right = heap.extractMin(); // extract next smallest

extract second smallest frequency node to merge

const merged = new Node(null, left.freq + right.freq, left, right); // merge nodes

create new internal node with combined frequency

heap.insert(merged); // insert merged node back

insert merged node back to heap to continue building tree

if (node.char !== null) { codes[node.char] = prefix; // assign code to character }

assign binary code to leaf character node

generateCodes(node.left, prefix + '0', codes); // left edge is 0

traverse left subtree adding '0' to code

generateCodes(node.right, prefix + '1', codes); // right edge is 1

traverse right subtree adding '1' to code

Output

f: 0

a: 1100

b: 1101

c: 100

d: 101

e: 111

Complexity Analysis

Time: O(n log n) because building the heap and merging nodes requires log n operations for each of the n characters

Space: O(n) because we store nodes and codes for each character

vs Alternative: Compared to fixed-length encoding which uses same bits per char, Huffman reduces average bits by assigning shorter codes to frequent chars

Edge Cases

empty frequency map

returns null tree and empty codes

DSA Javascript

while (heap.size() > 1) {

single character frequency

code assigned is empty string or '0' since only one node exists

DSA Javascript

while (heap.size() > 1) {

When to Use This Pattern

When you need to compress data by assigning variable-length codes based on frequency, reach for Huffman Encoding because it builds an optimal prefix tree.

Common Mistakes

Mistake: Not using a priority queue or min-heap to pick smallest frequencies efficiently
Fix: Use a min-heap data structure to always merge the two smallest frequency nodes

Mistake: Assigning codes without ensuring prefix property (codes not unique prefixes)
Fix: Build tree and assign codes by traversing left as '0' and right as '1' to guarantee prefix-free codes

Summary

Builds a tree to assign shorter binary codes to frequent characters for efficient compression.

Use when you want to compress data by encoding characters with variable-length codes based on frequency.

The key insight is merging the two least frequent nodes repeatedly to build a prefix-free binary tree.

Practice

1. What is the main goal of Huffman Encoding in data compression?

easy

A. To encrypt data for security

B. To assign shorter codes to more frequent characters

C. To assign equal length codes to all characters

D. To sort characters alphabetically

Solution

1. Step 1: Understand Huffman Encoding purpose

   Huffman Encoding compresses data by using shorter codes for frequent characters and longer codes for less frequent ones.

2. Step 2: Compare options with this purpose

   Only To assign shorter codes to more frequent characters matches this goal; others describe different concepts.

3. Final Answer:

   To assign shorter codes to more frequent characters -> Option B

4. Quick Check:

   Huffman Encoding = shorter codes for frequent chars [OK]

Hint: Remember: frequent chars get shorter codes in Huffman [OK]

Common Mistakes:

• Thinking Huffman assigns equal length codes
• Confusing compression with encryption
• Assuming alphabetical sorting is the goal

2. Which of the following is the correct way to represent a node in a Huffman tree in JavaScript?

easy

A. const node = 'a:5';

B. const node = [ 'a', 5, null, null ];

C. const node = function(char, freq) { this.char = char; this.freq = freq; };

D. const node = { char: 'a', freq: 5, left: null, right: null };

Solution

1. Step 1: Identify proper node structure for Huffman tree

   A node should store character, frequency, and pointers to left and right children.

2. Step 2: Check each option

   const node = { char: 'a', freq: 5, left: null, right: null }; uses an object with char, freq, left, right properties which is clear and correct. const node = [ 'a', 5, null, null ]; uses an array without labels, making it unclear. const node = function(char, freq) { this.char = char; this.freq = freq; }; is a constructor but incomplete (no left/right). const node = 'a:5'; is a string, not a node.

3. Final Answer:

   const node = { char: 'a', freq: 5, left: null, right: null }; -> Option D

4. Quick Check:

   Node = object with char, freq, left, right [OK]

Hint: Use objects with named properties for tree nodes [OK]

Common Mistakes:

• Using arrays without labels for nodes
• Using strings instead of objects
• Missing left and right child pointers

3. Given the frequencies: {'a': 5, 'b': 9, 'c': 12, 'd': 13}, what is the Huffman code for character 'a' after building the tree?

medium

A. 00

B. 111

C. 110

D. 10

Solution

1. Step 1: Build Huffman tree from frequencies

   Combine lowest frequencies: 5('a') and 9('b') -> node with freq 14. Then combine 12('c') and 13('d') -> node with freq 25. Finally combine 14 and 25 -> root 39.

2. Step 2: Assign codes by traversing tree

   Left edges get '0', right edges get '1'. 'a' is left child of first combined node, so code is '110'.

3. Final Answer:

   110 -> Option C

4. Quick Check:

   Lowest freq char 'a' gets code '110' [OK]

Hint: Combine lowest freq nodes first, assign 0 to left [OK]

Common Mistakes:

• Assigning codes without building tree
• Mixing left/right code bits
• Ignoring frequency order

4. Consider this JavaScript snippet for building a Huffman tree:

function buildTree(freqMap) {
  let nodes = Object.entries(freqMap).map(([char, freq]) => ({char, freq}));
  while(nodes.length > 1) {
    nodes.sort((a,b) => a.freq - b.freq);
    let left = nodes.shift();
    let right = nodes.shift();
    let newNode = {char: null, freq: left.freq + right.freq, left, right};
    nodes.push(newNode);
  }
  return nodes[0];
}

What is the bug in this code?

medium

A. The function does not handle empty freqMap

B. The newNode should not have char property

C. The nodes array is not updated correctly after push

D. The nodes array is not sorted before each iteration

Solution

1. Step 1: Analyze function behavior with empty input

   If freqMap is empty, Object.entries(freqMap) is empty array, so nodes is empty. The while loop condition nodes.length > 1 is false, so function returns nodes[0], which is undefined.

2. Step 2: Identify missing edge case handling

   The function does not check for empty freqMap and returns undefined instead of a valid tree or null.

3. Final Answer:

   The function does not handle empty freqMap -> Option A

4. Quick Check:

   Empty input returns undefined, missing edge case [OK]

Hint: Check empty input cases in tree-building functions [OK]

Common Mistakes:

• Assuming nodes always have elements
• Ignoring empty input edge cases
• Thinking sorting is missing when it is present

5. You have the string "abbcccdddd". Using Huffman Encoding, what is the minimum total number of bits needed to encode this string? Frequencies: a=1, b=2, c=3, d=4.

hard

A. 19 bits

B. 17 bits

C. 15 bits

D. 21 bits

Solution

1. Step 1: Build Huffman tree and assign codes

   Frequencies: a=1, b=2, c=3, d=4. Combine a(1) and b(2) -> node(3). Combine node(3) and c(3) -> node(6). Combine node(6) and d(4) -> root(10). Assign codes: d=0 (1 bit), c=10 (2 bits), b=110 (3 bits), a=111 (3 bits).

2. Step 2: Calculate total bits

   Total bits = (a:1*3) + (b:2*3) + (c:3*2) + (d:4*1) = 3 + 6 + 6 + 4 = 19 bits.

3. Final Answer:

   19 bits -> Option A

4. Quick Check:

   Sum(freq * code length) = 19 bits [OK]

Hint: Multiply frequency by code length, then sum all [OK]

Common Mistakes:

• Adding frequencies instead of weighted bits
• Assigning wrong code lengths
• Ignoring frequency when calculating total bits