How exactly can the Huffman's algorithm be implemented in the linearithmic time?

Does anybody here understand how can the Huffman's algorithm be implemented in linearithmic ( O(n*log(n)) ) time? The way I implemented it in the AEC programming language (you can see it live here and you can see the code here), it takes O(n^2) time.

Huffman's algorithm requires one to first count the frequencies of the characters and store them in an array of TreeNodes. I did that in O(n^2), but I guess it can be done in O(n*log(n)) by using a set and then converting that set to an array. But then it requires us to, in the worst case (all the characters are different and the string cannot be compressed), n times search for the node with the lowest frequency and the node with the second-lowest frequency in the array of TreeNodes. How can that possibly be done in any less than O(n^2) time? And it requires us to erase those minimal nodes from the array when we find them. Deleting an element from an array takes O(n) time. And if we do that n times, it takes O(n^2) time, right? So, how can Huffman's algorithm possibly be implemented in O(n*log(n)) time?

I think your mistake is in thinking n to be a constant in this context.  As you delete an item from the list, the list essentially shrinks.  So n is constantly decreasing as you do the deletions.  No? 

If I knew how to write math notation, I would show that the total number of operations while searching for the new most often used symbol would be a sum of each value of m from n to 1.  Hmmmm

But that is similar to the area of a triangle, so 1/2 * n^2. 

So, what is wrong here?

Here's a reference.  Maybe this will give some insight?

https://www.topcoder.com/thrive/articles/huffman-coding-and-decoding-algorithm

Might you be thinking of Adaptive Huffman Encoding?
https://en.m.wikipedia.org/wiki/Adaptive_Huffman_coding

I guess it depends on where you're asking this from.

If you're asking as a student then I'd say post the pseudo code.  Maybe something will stand out to someone.

If you're asking as a profession then first why AEC and not Matlab or C like a normal person?  Also have you tried stealing it from somewhere first?

If you're asking as a profession then first why AEC and not Matlab or C like a normal person?

AEC is the programming language I designed and implemented. I think that programming in a language you've made yourself is a good thing because it's the only way of avoiding bugs that come from misunderstanding the programming language you are using. Most of the bugs I've run into in my hobby projects came from me misunderstanding the language I was using.

I think that programming in a language you've made yourself is a good thing because it's the only way of avoiding bugs that come from misunderstanding the programming language you are using.

Didn't you write the AEC in Javascript?

Quote from: FlatAssembler on June 07, 2024, 01:32:50 AM

I think that programming in a language you've made yourself is a good thing because it's the only way of avoiding bugs that come from misunderstanding the programming language you are using.

Didn't you write the AEC in Javascript?

Well, the first compiler I wrote for AEC, one which targets x86, is written in JavaScript. But the one I was using to compile the Huffman's Coding in AEC, the one that targets WebAssembly, is written in C++.