java - 为什么在执行 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']？

任何帮助，将不胜感激。

标签： javadata-structurespriority-queue

Answer 1

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

您可以在此处阅读有关堆的更多信息，并在此处阅读有关树遍历的更多信息