Re: Huffman Encoding?

[Roy Grimm <ragrimm@bigfoot.com>]

Mark wrote:
> 
> I'm currently writing a program that produces Huffman Encoding for text
> input.  I'm trying to determine the best data structure to utilize for
> sorting the character frequencies.  I used a linked-list of records to
> store 1)character,
> 2)frequency, and 3) marked/unmarked.  (with the linked-list sorted
> according to character)  From here I intended to populate the binary
> tree, but must first sort according to frequency. I feel that there must
> be a cleaner alternative.  Has anyone done this, and if so what did you
> find to be the best approach?

When I wrote my Huffman encoder for my graduate algorithms class (which
is the only reason most people would bother doing it...), I used a
method of storing the bounded list of character frequency in a data
structure that had O(1) lookup time.  I'll leave the implementation as
an exercise for the reader.

p.s.  If you're looking to optimise space, there is a way to eliminate
one field from your list of elements.  That's an exercise for the
advanced students...

-- 
Roy A. Grimm

Mathematics and alcohol don't mix. Don't drink and derive.