트리 생성은 자식 노드에서 부모 노드로 가는 상향식으로 작동한다. 이런 특정 트리의 왼쪽 서브 트리는 다음과 같은 연산의 결과이며, 이와 같은 방식으로 계속하면 전체 트리를 만들 수 있다.

n1 ← CreateTree(7, NULL, NULL)

n2 ← CreateTree(1, NULL, NULL)

n3 ← CreateTree(5, n1, n2)

인코딩을 생성하는 데 필요한 두 번째 자료 구조는 우선순위 큐(priority queue)다. 우선순위 큐는 아이템을 제거할 때 최대 우선순위 큐인지 또는 최소 우선순위 큐인지에 따라 가장 큰 값(max-priority) 또는 가장 작은 값(min-priority)을 갖는 아이템을 먼저 제거한다. 최대 우선순위 큐는 아이템을 제거할 때 가장 큰 값을 갖거나 우선순위가 가장 높은 아이템을 제거한다. 그다음 다시 아이템을 제거할 때는 남아 있는 아이템에서 가장 큰 값을 갖는 아이템을 제거하므로 제거되는 아이템은 두 번째 우선순위인 아이템이다. 역으로 최소 우선순위 큐에서는 가장 낮은 우선순위를 갖는 아이템을 제거하고 그다음 두 번째로 낮은 우선순위의 아이템을 제거하는 식이다. 결국 우선순위 큐는 다음 연산을 따른다.

• CreatePQ() 빈 우선순위 큐를 생성한다.

• InsertInPQ(pq,i) 우선순위 큐 pq에 아이템 i를 삽입한다.

• FindMinInPQ(pq) 또는 FindMaxInPQ(pq) 최소 우선순위 큐에서는 큐에 있는 아이템 중 최솟값을 반환하고 최대 우선순위 큐에서는 큐에 있는 아이템 중 최댓값을 반환한다. FindMinInPQ(pq)와 FindMaxInPQ(pq)는 최솟값 또는 최댓값을 반환하지만, 큐를 변경하지 않으며 값도 그대로 남아 있다.

• ExtractMinFromPQ(pq) 또는 ExtractMaxFromPQ(pq) 최소 우선순위 큐에서는 큐에 있는 아이템 중 최솟값을 제거하고 반환하며, 최대 우선순위 큐에서는 큐에 있는 아이템 중 최댓값을 제거하고 반환한다.

• SizePQ(pq) 우선순위 큐 pq에 있는 아이템 수를 반환한다.