0

I'm working (rather beginning) on a Huffman tree. I think I've run in to a problem for time complexity.

Huffman trees are supposed to be fast in most ways.

As I prepare to build my tree, I have three for...next loops in separate methods.

I think that could be very bad time complexity. I think its something like n^3, which isn't just bad its atrocious. n^2 is bad enough. This is only the initialization process that these loops are running at.

One method goes through a 27 length array of FrequentChars (a container class I invented, much like a C struct) and gives each element a new frequentChar, and default values in alphabetical order. The last position (#26) belongs to space characters.

Next I have a findFrequencies() method which goes through the string I'm given, finding where each character occuring belongs and increments the associated frequency inside the freqChars array.

Next I have another loop which places each char and frequency in a priority queue just before building the tree. The Priority Queue and the Tree classes were given to us (I'm taking a class on Advanced data structures and algorithms), and I've modified them to suit my needs. The priorityQueue class can contain Tree elements, and will be used to assemble the tree.

I just feel like this is grossly inefficient. I've been stressed out with other work for some time now, and haven't been able to put much work in to this since it was assigned almost two weeks ago. I'm a fairly proficient programmer, I can make things work, but I don't have much experience making things work well.

I just realized that I have to add yet another for...next loop just to know how big to make my priority queue. The Queue takes a size parameter in its constructor. I could modify the Priority queue class to be dynamic too, but that only just occurred to me.

Am I right about this?

OH and I would provide my code, but it would take up a ton of space and I don't think I can post the instrutors classes without permission.

Edited by Curious Gorge

2
Contributors
1
Reply
13
Views
1 Year
Discussion Span
Last Post by rubberman
0

Are these sorted arrays? If so, can't you use bsearch to find the position needed? And if you need to insert a new element, then use a modified bsearch algorithm that will return the insert position in a passed pointer or reference variable (depending upon whether you want a C or C++ method). IE, if the function returns NULL (not found), the insert position would be in the passed insert_posn variable. The signature for standard bsearch is void* bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
The modified version could be:
void* posn_bsearch(const void *key, const void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *), size_t* insert_posn);
Since this is open source, making a modified version is trivial. I did it myself for sorted collection classes I wrote for the FACTORYworks MES system.

So, if you pass a NULL value for insert_posn, it can behave just like bsearch.

Edited by rubberman

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.