Huffman Encoding in DSA Typescript - 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 letters and longer codes for rare letters. 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. It helps assign codes to characters based on their frequency.

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'. Leaves represent characters with their codes.

intermediate

Why does Huffman Encoding produce a prefix code?

Because no code is the start of another code, so decoding is easy and unambiguous. This happens naturally from the tree structure.

advanced

What is the time complexity to build a Huffman Tree for n unique characters?

It is O(n log n) because we use a priority queue to pick the two smallest frequencies repeatedly until one tree remains.

What does Huffman Encoding use to decide code lengths?

A Character frequency

B Alphabetical order

C Character ASCII value

D Random assignment

Huffman Encoding assigns shorter codes to characters that appear more often, based on their frequency.

In Huffman Tree, what does a leaf node represent?

A A character and its code

B A frequency sum

C An internal node

D A code prefix

Leaf nodes represent actual characters with their assigned codes.

What is the first step in building a Huffman Tree?

A Build a balanced binary tree

B Create leaf nodes for each character with frequency

C Assign codes randomly

D Sort characters alphabetically

We start by creating leaf nodes for each character with their frequency.

Why is Huffman Encoding called a lossless compression?

A Because it changes data format

B Because it removes some data

C Because it uses lossy codes

D Because original data can be perfectly restored

Huffman Encoding allows exact recovery of original data, so no information is lost.

Which data structure helps efficiently pick the two smallest frequencies in Huffman Encoding?

A Stack

B Queue

C Priority queue (min-heap)

D Linked list

A priority queue or min-heap helps pick the two smallest frequency nodes quickly.

Explain how Huffman Encoding builds the tree and assigns codes to characters.

Think about combining smallest frequencies step by step.

Why is Huffman Encoding efficient for data compression compared to fixed-length codes?

Consider how code length relates to character frequency.