Is there are particular reason why it would be advantageous to use a heap here as opposed to a different kind of sort? On most of the other problems we use heaps because they allow us to reduce the space complexity and turn an nlogn into an nlogk operation. In this problem, there doesn’t seem to be a reason to use heapsort over any other kind of sort.
It makes sense to use this approach when we have a lot of duplicate characters, because we’ll get a running time that’s very close to linear. If you imagine using a quick sort, you still have to compare every other character by its frequency even though they are same. You could argue that a small tweak could make quicksort linear in this particular situation however heapsort does remove unnecessary time complexity by its nature.