Huffman - Algorithm

Huffman's greedy algorithm:

$1.$ Create a leaf node for each character with its frequency.

$2.$ Put all nodes in a min-heap (by frequency).

$3.$ While heap has more than $1$ node:

• Extract two minimum frequency nodes.
• Create a new internal node with these as children.
• Insert the new node with frequency = sum.

$4.$ The remaining node is the root. Edges to left are $0$, to right are $1$. A character's code is the path from root to leaf. Time: $O(n \log n)$. Space: $O(1)$.