为什么在执行 poll() 时优先级队列会重新排序元素？

Question

今天当我从优先队列中poll() 元素时，我意识到在poll() 元素之后，队列中的其余元素改变了顺序。基本上我有优先级队列，我重写了 Comparator 方法让它们按它在字符串中出现的次数排序（最大堆）

Queue<Character> pq = new PriorityQueue<>(new Comparator<Character>(){
    @Override
    public int compare(Character a, Character b) {
        if(map.get(a) == map.get(b)) {
            return map.get(a) - map.get(b);
        }
        return map.get(b) - map.get(a);
    }
});

如果我有一个字符串“aabbcc”，每个字符出现的频率将为

['a':2, 'b':2, 'c':2]

优先队列将是

['a','b','c']

当我执行 poll() 时，优先级队列变为：

['c', 'b']

为什么不 ['b','c']?

如有任何帮助，我们将不胜感激。

Answer 1

PriorityQueues 将其元素存储在堆中（默认情况下为最小堆，但这可以通过 Collections.reverseOrder() 传递给构造函数来更改）。此数据结构仅保证第一个元素或从 poll() 收到的元素将是队列中基于元素自然排序的最小元素。当一个对象被移除时，队列被“堆化”以保证最小元素将是下一个被轮询的元素。当您通过调用 toString 方法打印队列时，堆将按级别顺序遍历打印，这不一定代表元素的存储方式。

您可以阅读有关堆的更多信息here, and about tree traversals here

为什么在执行 poll() 时优先级队列会重新排序元素？

Why priority queue re-order element when I do poll()?

java

priority-queue

data-structures