import Collections

procedure main(A)
    every line := !&input do {
        every (t := table(0))[!line] +:= 1           # Frequency table
        heap := Heap(sort(t), field, "<")            # Initial priority queue
        while heap.size() > 1 do {                   # Tree construction
            every (p1|p2) := heap.get()
            heap.add([&null, p1[2]+p2[2], p1, p2])
            }
        codes := treeWalk(heap.get(),"")             # Get codes from tree
        write("Huffman encoding:")                   # Display codes
        every pair := !sort(codes) do
            write("\t'",\pair[1],"'-> ",pair[2])
        }
end

procedure field(node)  # selector function for Heap
    return node[2]  # field to use for priority ordering
end

procedure treeWalk(node, prefix, codeMap)
    /codeMap := table("")
    if /node[1] then {  # interior node
        treeWalk(node[3], prefix||"0", codeMap)
        treeWalk(node[4], prefix||"1", codeMap)
        }
    else codeMap[node[1]] := prefix
    return codeMap
end