The algorithm
PriorityQueue pq = new PriorityQueue<>((a, b) -> a.freq - b.freq);
for (Symbol s : symbols) pq.offer(new Node(s, s.freq));
while (pq.size() > 1) {
Node left = pq.poll(), right = pq.poll();
Node parent = new Node(null, left.freq + right.freq);
parent.left = left; parent.right = right;
pq.offer(parent);
}
Node root = pq.poll();
// Traverse: left = '0', right = '1', leaves have codes Advertisement
Why greedy is optimal
Optimal prefix tree has two least-frequent symbols as siblings at max depth. Combining them optimally builds up the tree.
Advertisement
Complexity
O(N log N) — N pops from PQ each O(log N).
Practical use
DEFLATE (gzip). JPEG DCT coefficients. Any variable-length encoding with known frequencies.