I don’t think the issue is with your understanding of priority queues. This code fails due to other reasons.
frequency.get(a) != frequency.get(b)
You are comparing objects, not primitive ints. You can solve this by casting one of the objects as such
(int) frequency.get(a) != frequency.get(b)
If both have same frequency, you need to compare them in alphabetical order.
Compares them yet again on their frequency.
Change it into this
These two changes should fix your issue.