medium

Huffman Coding

Given symbols with their frequencies, construct a binary prefix code that minimises the total encoded length Σ frequency × code length. Return the minimum total length (or the codes themselves).

Constraints

2 ≤ number of symbols ≤ 10^5
1 ≤ frequency ≤ 10^9

Examples

in: freq = {a: 45, b: 13, c: 12, d: 16, e: 9, f: 5}

out: 224

Codes of lengths 1, 3, 3, 3, 4, 4.

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.