type block
    freq as uinteger
    chars as string
end type

type code
    char as string*1
    code as string
end type

sub bubble( lst() as block, n_l as uinteger )
    for j as integer = n_l-1 to 0 step -1
        if j>0 andalso lst(j).freq > lst(j-1).freq then
            swap lst(j), lst(j-1)
        endif
    next j
end sub

dim as string Sample = "this is an example for huffman encoding"
redim as block hufflist(0)
hufflist(0).freq = 1 : hufflist(0).chars = mid(Sample,1,1)
dim as boolean newchar
dim as string*1 currchar
dim as uinteger n_h = 1, n_c

'read characters in one-by-one and simultaneously bubblesort them
for i as uinteger = 2 to len(Sample)
    currchar = mid(Sample,i,1)
    newchar = true
    for j as uinteger = 0 to n_h-1
        if mid(Sample,i,1) = hufflist(j).chars then
            hufflist(j).freq += 1
            newchar = false
        end if
        if j>0 andalso hufflist(j).freq > hufflist(j-1).freq then
            swap hufflist(j), hufflist(j-1)
        endif
    next j
    if newchar then
        redim preserve hufflist(0 to n_h)
        hufflist(n_h).chars = currchar
        hufflist(n_h).freq  = 1
        n_h+=1
    end if
next i
'one final pass of bubblesort may be necessary
bubble hufflist(), n_h

'initialise huffman code
redim as code codelist(0 to n_h-1)
for i as uinteger = 0 to n_h-1
    codelist(i).char = hufflist(i).chars
    codelist(i).code = ""
next i
n_c = n_h

do
    'characters in the least common block get "0" appended
    for i as uinteger = 1 to len(hufflist(n_h-1).chars)
        for j as uinteger = 0 to n_c-1
            if codelist(j).char = mid(hufflist(n_h-1).chars,i,1) then
                codelist(j).code = "0" + codelist(j).code
            end if
        next j
    next i
    'characters in the second-least common block get "1" appended
    for i as uinteger = 1 to len(hufflist(n_h-2).chars)
        for j as uinteger = 0 to n_c-1
            if codelist(j).char = mid(hufflist(n_h-2).chars,i,1) then
                codelist(j).code = "1" + codelist(j).code
            end if
        next j
    next i
    'combine the two least frequent blocks
    hufflist(n_h-2).chars = hufflist(n_h-2).chars + hufflist(n_h-1).chars
    hufflist(n_h-2).freq = hufflist(n_h-2).freq + hufflist(n_h-1).freq
    redim preserve hufflist(0 to n_h-2)
    n_h -= 1
    'move the new combined block to its proper place in the list
    bubble hufflist(), n_h
loop until n_h = 1

for i as uinteger = 0 to n_c - 1
    print "'"+codelist(i).char+"'", codelist(i).code
next i