Java PriorityQueue Unexpected Order for Poll()

Question

I have a question regarding the sorting order of Java PriorityQueue.

I have a map to count the frequency of the characters in a String s.

Then I added all the entries in the PriorityQueue, I wrote a customize sorting function based on the frequency(value of the entry), if the frequency is the same, then return smaller character first. i.e. Desc for frequency, Asc for Characters.

Here is the problem,

if my input is a -> 10, b -> 10, c -> 10, when I poll the entry out from the heap, it's expected to return in the order : a -> b -> c

current top : a
current top : b
current top : c

However, if my input is a -> 500, b -> 500, c -> 500, the return order is a -> c -> b.

current top : a
current top : c
current top : b

This is confusing, I am wondering what is the root cause for this? I know the iterator of the heap is not order guarantee, but the poll() should return the first element for me every time. Am I misunderstanding anything?

Thanks

Map<Character, Integer> map = new HashMap<>();
for(char ch : s.toCharArray())
    map.put(ch, map.getOrDefault(ch, 0) + 1);

PriorityQueue<Map.Entry<Character,Integer>> heap = new PriorityQueue<>(
    (a, b) -> a.getValue() == b.getValue() ? a.getKey().compareTo(b.getKey()) : b.getValue().compareTo(a.getValue())
);
heap.addAll(map.entrySet());

while(!heap.isEmpty()) {
    Map.Entry<Character,Integer> top = heap.poll();
    System.out.println("current top : " + top.getKey());
}