英文:
Why priority queue re-order element when I do poll()?
问题
今天当我从优先队列中使用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']？
任何帮助将不胜感激。
英文:
Today when I poll() element from priority queue, I realized after poll() element, the rest of element in queue change the order. basically I have priority queue and I override Comparator method to let them order by how many time it show up in string (max heap)
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);
}
});
if I have a string "aabbcc", the frequency of each character will be
['a':2, 'b':2, 'c':2]
and priority queue will be
['a','b','c']
when I did poll(), the priority queue become to:
['c', 'b']
why not ['b','c']?
Any help would be appreciated.
答案1
得分: 1
PriorityQueues 将它们的元素存储在堆中（默认情况下为小根堆，但可以通过在构造函数中传递 Collections.reverseOrder() 来更改）。该数据结构仅保证第一个元素或从 poll() 中接收的元素将是基于元素的自然顺序的最小元素。当删除对象时，队列将进行“堆化”以保持最小元素将是下一个被轮询的元素的保证。通过调用 toString 方法打印队列时，堆将以层序遍历的方式打印出来，这不一定代表元素的存储方式。
您可以在这里了解更多关于堆的信息1，以及关于树遍历的信息2。
英文:
PriorityQueues store their elements in a heap (a min heap by default, but this can be changed with Collections.reverseOrder() passed to the constructor). This data structure only guarantees that the first element, or the element received from poll() will be the smallest element in the queue based on the natural ordering of the elements. When an object is removed, the queue is "heapified" to maintain the guarantee that the minimum element will be the next one polled. When you print the queue by calling the toString method, the heap is getting printed in a level order traversal, which is not necessarily representative of how the elements are being stored.
You can read more about heaps here, and about tree traversals here
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论