The other main point is string handling, which pretty consistently uses repeated concatenation here (e.g. for building prefixes (that one is mostly a non-concern though, since even with slow string concat, it'll be linearithmic time), for encoding / decoding). At least the encoding could be rewritten to use an array without making it any less readable.

Arguably all of this is fine in practice, as JS engines optimize string concatenation. I think it needs some comments alluding to this, though (I'm thinking something along the lines of "the string concatenation in a loop here is fine despite strings being immutable, as modern JS engines optimize it to be amortized constant time by delaying it (using ropes) and similar techniques").

I'm sorry about the unrelated changes due to formatting, that's due to a mistake on our part (see#1515).

Keep up the good work!

Why have you duplicated the code? I think there should only be a heap-based implementation; it is strictly better (more efficient) than the array-based one and of similar code complexity.