Implementation with Local Minimum Compatible Pairs

Initialization
for ( $k\!\!=\!\!1; \; k\!\leq\! N;\;k\!$++ )
Initialize T[k]
$A[k] = address\_of (T[k])$
End:Initialization

Main Loop
for ( $k\!\!=\!\!1; \; k\!<\!N;\;k\!$++)
Initialize the search for l.m.c.p from the beginning of the
working sequence.
while(1)
# This loop looks for l.m.c.p. When it finds it combines the nodes
# in the pair and exits the while loop.
Locate the two nodes with least weight in the current
Huffman Sequence.
Let the A[i] and A[j] point to the element with the smallest and next
to smallest weights respectively within the current
Huffman Sequence.
if( both A[i] and A[j] point to internal nodes )
then
#This is a $\mathbf{l.m.c.p}\Rightarrow$ Combine the two nodes:
$\mathsf{CombineNodes(A[i], A[j])}$
1. Create a new node I
I.position = min(i,j)
I.type = INTERNAL
$I.weight = \sum$(weights of the nodes pointed by A[i] and A[j])
I's left and right tree pointers = A[i] and A[j]
2. Update the array A[N]:
if (i<j)
then
$A[i]=address\_of(I)$
A[j]=null
else
$A[j]=address\_of(I)$
A[i]=null
${end:}\mathsf{CombineNodes()}$
break
else
#One of the nodes is a terminal node
if (the right node is a terminal node)
then
$\mathbf{if} (\exists$ node from the right adjacent Huffman Sequence with
smaller weight than the left node of the pair )
then
Resume the search for l.m.c.p. from the current
Huffman Sequence
continue
else
# l.m.c.p is found
$\mathsf{CombineNodes(A[i], A[j])}$
break
else
# l.m.c.p. is found
$\mathsf{CombineNodes(A[i], A[j])}$
break
End: while
End: Main Loop
End: Phase I Completed