Re: Huffman Encoding?

[mcc@entropy.cs.princeton.edu (Martin C. Carlisle)]

Actually, at an undergraduate level (where we give a very similar assignment)
I would expect the students to understand a heap data structure.  
It can be created in linear time (vice nlogn for comparison based sorts),
and allows extracting the minimum and inserting new items (both required for
Huffman [the standard algorithm for it anyway]) in logarithmic time.

With a linked list, you have O(n) insert, but O(1) extract min.

--Martin

ps.  You can sort 5 elements in constant time.

In article <3708B1B2.715FC009@bigfoot.com>,
Roy Grimm  <ragrimm@bigfoot.com> wrote:
>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

>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.


-- 
Martin C. Carlisle, Asst Prof of Computer Science, US Air Force Academy
carlislem@acm.org, http://www.usafa.af.mil/dfcs/bios/carlisle.html
DISCLAIMER:  This content in no way reflects the opinions, standards or 
policy of the US Air Force Academy or the United States Government.