From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID autolearn=no autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,4e1d151165b800f2 X-Google-Attributes: gid103376,public From: mcc@entropy.cs.princeton.edu (Martin C. Carlisle) Subject: Re: Huffman Encoding? Date: 1999/04/05 Message-ID: <7eard5$djd$1@cnn.Princeton.EDU>#1/1 X-Deja-AN: 462934631 References: <37083AFF.AD3306A2@bellatlantic.net> <3708B1B2.715FC009@bigfoot.com> Organization: US Air Force Academy, Dept of Computer Science Newsgroups: comp.lang.ada Date: 1999-04-05T00:00:00+00:00 List-Id: 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 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.