You can't do it faster than O(n log n) for the simple reason that you need to sort the frequencies. If the symbols come sorted, then you can do it in O(n) time

You can't do it faster than O(n log n) for the simple reason that you need to sort the frequencies. If the symbols come sorted, then you can do it in O(n) time, yes, using two queues.