Huffman Encoding in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is Huffman Encoding?

Huffman Encoding is a way to compress data by using shorter codes for common characters and longer codes for rare ones. It builds a tree to assign these codes so the total size is smaller.

beginner

What data structure is mainly used in Huffman Encoding?

A binary tree called the Huffman Tree is used. Each leaf node represents a character, and the path from root to leaf gives the character's code.

intermediate

How are the codes assigned in Huffman Encoding?

Codes are assigned by traversing the Huffman Tree: going left adds '0' and going right adds '1'. This creates unique prefix codes for each character.

advanced

Why does Huffman Encoding produce optimal prefix codes?

Because it always combines the two least frequent characters first, building the tree from bottom up, ensuring the shortest codes go to the most frequent characters.

intermediate

What is the role of a priority queue in Huffman Encoding?

A priority queue helps pick the two smallest frequency nodes quickly to merge them when building the Huffman Tree.

What does each leaf node in a Huffman Tree represent?

A A character and its frequency

B A code prefix

C A merged frequency only

D An internal node

Each leaf node holds a character and its frequency from the input data.

In Huffman Encoding, what bit is added when moving to the left child in the tree?

A 1

B Depends on frequency

C 0

D No bit is added

Going left adds '0' to the code, going right adds '1'.

What is the main goal of Huffman Encoding?

A Compress data

B Search data

C Sort data

D Encrypt data

Huffman Encoding compresses data by assigning shorter codes to frequent characters.

Which algorithmic approach does Huffman Encoding use to build the tree?

A Dynamic programming

B Greedy

C Divide and conquer

D Backtracking

It uses a greedy approach by always merging the two smallest frequency nodes.

What data structure is commonly used to efficiently select the two smallest nodes during Huffman Tree construction?

A Stack

B Linked list

C Queue

D Priority queue

A priority queue allows quick access to the smallest frequency nodes.

Explain how the Huffman Tree is built from character frequencies.

Think about picking smallest frequencies and combining them step by step.

Describe how Huffman codes are assigned to characters once the tree is built.

Follow the path from root to leaves to get codes.