Huffman Coding

The Secret Scroll has to cross the mountains on a raven, and the raven is paid by the bit. Written the plain way, with 8 bits for every symbol, ABRACADABRA costs 11 × 8 = 88 bits. The scroll keeper has a better plan: give common symbols short codes and rare ones long codes, with no code being the start of another (so the reader always knows where one symbol ends).

The keeper builds the codes like this:

1. Count how often each distinct symbol appears. Each symbol starts as its own node, weighing its count.
2. Take the two lightest nodes and join them under a new node that weighs their sum. Put the new node back.
3. Repeat until one tree is left. A symbol's code is its path from the root: left is 0, right is 1.

Write encoded_length(symbols: list[str]) -> int: the total number of bits the whole scroll takes with these codes (the sum, over every symbol in the scroll, of the length of its code).

encoded_length(list("ABRACADABRA"))
# 23    A appears 5 times, B 2, R 2, C 1, D 1.
#       Join C+D (2), then B+R (4), then those two (6), then A with it (11).
#       A gets a 1-bit code, the other four get 3 bits: 5·1 + (2+2+1+1)·3 = 23

encoded_length(["fire", "ice", "fire", "bolt", "fire", "ice"])   # 9    fire: 1 bit, ice and bolt: 2 bits
encoded_length(["hush", "hush", "hush"])                         # 3    only one symbol: its code is "0"
encoded_length([])                                               # 0

When several nodes weigh the same, you may join any of the lightest: the trees can differ, but the total number of bits is always the same, and it's the smallest any prefix-free code can reach.

• A scroll has 0 <= len(symbols) <= 2 * 10^5 symbols; each symbol is 1 to 8 letters or digits, and there may be up to 2 * 10^5 distinct ones.
• One distinct symbol gets the code "0", so each copy costs 1 bit.
• Scanning all the nodes for the two lightest on every join is O(k²) for k distinct symbols: too slow when k is 10⁵. Aim for O(n + k log k).