java - PriorityQueue 更改 poll() 上的元素位置

Question

我在使用优先级队列时遇到了一些问题。不幸的是我的谷歌研究没有结果:(我希望有人可以帮助我。

我正在使用优先级队列通过名为“reachabilityDistance”的特定属性对某些对象进行排序，该属性是一个简单的 double 值。将对象插入队列可以正常工作并产生正确的排序。但随后我想轮询队列的第一个对象，而其他对象的顺序会发生变化，即使它们的值保持不变。这有什么问题吗？

private PriorityQueue<ClusteringObject> orderedSeedQueue;
...
orderedSeedQueue = new PriorityQueue<>(clusteringObjects.size(), new ReachabilityObjectComperator());
while (!orderedSeedQueue.isEmpty()) {
            clusteringObject = orderedSeedQueue.poll();
            calculateNeighborhood(clusteringObject, clusteringObjects);
            clusteringObject.setProcessed();
            clusteringObject.setCoreDistance(minNeighbors);
            resultClusterList.add(clusteringObject);
            updateSeedQueue(clusteringObject.getNeighbors(), clusteringObject);
        }

这是我正在使用优先级队列的代码片段。在 updateSeedQueue 方法中，一些值将分别插入到该队列中并进行更新(删除并再次添加)。这对我来说效果很好，但是每次执行 poll() 时，所有正确排序的条目都会得到错误的顺序。

这是我的比较器:

public class ReachabilityObjectComperator implements Comparator<ClusteringObject> {

@Override
public int compare(ClusteringObject x, ClusteringObject y) {
    if (x.getReachabilityDistance() < y.getReachabilityDistance()) {
        return -1;
    } else if(x.getReachabilityDistance() > y.getReachabilityDistance()) {
        return 1;
    } else {
        if(x.getMetadataIndex() < y.getMetadataIndex()) {
            return -1;
        } else if(x.getMetadataIndex() > y.getMetadataIndex()) {
            return 1;
        } else {
            return 0;
        }
    }
}

}

所以我的问题又来了:为什么 poll() 会改变这个队列中剩余对象的顺序？

Answer 1

PriorityQueue 仅声称以正确的顺序进行第一个条目。如果您迭代 PriorityQueue，您可以按任何顺序查看除第一个元素之外的所有元素，并且它可能会随着您添加/删除条目而更改。

来自 PriorityQueue 的 Javadoc

The Iterator provided in method iterator() is not guaranteed to traverse the elements of the priority queue in any particular order. If you need ordered traversal, consider using Arrays.sort(pq.toArray()).

如果您始终需要正确的排序，我建议使用 TreeSet。

NavigableSet<MyType> orderedSeedQueue = new TreeSet<>(new MyComparator());
// add elements

while(!orderSeedQueue.isEmpty()) {
     firstItem = orderSeedQueue.pollFirst();

但是，根据您的用例，对它们进行排序可能会更简单。

List<MyType> types = ...
Collections.sort(types, new MyComparator());
for(MyType t : types) { // in sorted order