w

이 과정은 알고리즘 3-1에 기술되어 있다. 먼저 알고리즘에 우선순위 큐를 전달한다. 우선순위 큐에 있는 각 원소는 문자와 문자의 빈도를 담고 있는 단일 원소 트리다. 알고리즘에서 노드에 저장된 데이터를 반환하는 함수 GetData(node)를 가정하는데, 여기서 데이터는 각 노드에 저장된 빈도다. 우선순위 큐가 하나 이상의 원소를 담고 있으면(1행) 알고리즘은 우선순위 큐에서 두 개의 원소를 꺼내(2~3행) 그 둘의 빈도를 더한(4행) 뒤 루트로 두 원소의 합을, 자식 노드로 두 개의 원소를 취하는 새로운 이진 트리를 생성하여(5행) 이 새로운 트리를 다시 큐에 넣는다(6행). 알고리즘이 끝날 무렵 우선순위 큐는 허프만 코드를 명시하는 하나의 이진 트리를 갖게 되고 큐에서 이 트리를 꺼내어 반환한다(7행). 문자의 인코딩을 찾으려면 루트에서 시작하여 문자에 해당하는 리프 노드에 도달할 때까지 트리를 탐색한다. 왼쪽으로 탐색할 때마다 인코딩에 0을, 오른쪽으로 탐색할 때마다 1을 넣는다. 결과 비트열은 문자의 허프만 인코딩이 된다. 그 결과로 이 예에서 E는 0, F는 100, C는 101이 되며, 앞의 표 3-7을 다 채울 때까지 다른 문자들에도 같은 방식이 적용된다.

▲ 그림 3-5 단어 effervescence의 허프만 코딩