PriorityQueue具有相同优先级的对象 [英] PriorityQueue has objects with the same priority

问题描述

我正在使用优先级队列来排序和使用大量自定义对象.对象具有权重"，即其自然顺序.但是，插入到优先级队列中的不同对象可能具有相同的权重".在这种情况下，我希望优先级队列按照它们放入队列的顺序对其进行排序.

I'm using a priority queue to sort and use a large number of custom objects. The objects have a "weight" that is their natural ordering. However, different objects that are inserted into the priority queue may have the same "weight". In such cases, I want the priority queue to order them in the same order in which they were put into the queue.

例如，如果我以相同的权重"顺序添加CustomObjects A，B，C，D，则优先级队列也应以该顺序返回它们-即使我轮询一个或多个在添加其他对象之前.

For example, if I add in CustomObjects A,B,C,D in that order, all with the same "weight", than the priority queue should return them in that order as well - even if I poll one or more of the objects before adding in the others.

这是我的自定义对象的CompareTo:

Here is the CompareTo for my custom object:

public int compareTo(CustomObject o) {
    int thisWeight = this.weight;
    int thatWeight = o.weight;
    if(thisWeight < thatWeight){
        return -1;
    }
    else{
        return 1;
    }
}

虽然我认为这可以保持最初的顺序，但事实并非如此.当我输入权重为1的A，B，C时会发生这种情况；民意测验A;并加上权重为1的D，E.不知何故，D和E在B之后但在C之前排序.

While I thought that this would maintain that initial order, it doesn't. This occurs when I input A,B,C with weight 1; poll A; and add D,E also with weight 1. Somehow, D and E are sorted after B, but before C.

我知道PriorityQueues的Iterator不能返回正确的顺序，因此查看顺序的能力受到限制-但是我可以看到元素离开队列的顺序，但显然没有遵循我想要的路径.

I am aware that the Iterator for PriorityQueues doesn't return the correct ordering, so I am limited in my ability to look at the ordering - however I can see the order that the elements leave the queue and it clearly doesn't follow the path that I want it to.

建议?

推荐答案

如果需要根据插入顺序进行排序，则需要在时间戳记中使用额外的元素.IE.在插入且权重相等时，请使用 timestamp 来查看首先插入哪个元素.因此 CustomObject 应该类似于:

If you need to have an ordering according the insertion order you need to use an extra element for timestamp. I.e. on insertions and equal weight use timestamp to see which element was inserted first. So CustomObject should be something like:

class CustomObject {  
   int weight;  
   long timestamp;  
}

比较应该是:

public int compareTo (CustomObject o) {  
    int thisWeight = this.weight;  
    int thatWeight = o.weight;  
    if (thisWeight != thatWeight) {  
        return thisWeight - thatWeight;  
    }  
    else {  
        return this.timestamp - o.timestamp;  
    }  
}  

较小的 timestamp 表示它是更早插入的，因此您可以按插入顺序进行操作.

The smaller timestamp means it was inserted earlier so you keep in the insertion order.

您还可以通过维护在每个 add 或 remove 上更新的计数器来使用逻辑"时间.

You could also use a "logical" time by maintaining a counter that you update on each add or remove.

这篇关于PriorityQueue具有相同优先级的对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！