使 Java PriorityQueue 成为稳定的优先级队列 [英] Making a Java PriorityQueue into a stable priority queue
问题描述
我正在尝试用 Java 实现一个稳定的(先进先出)优先级队列.假设键是名字,值是年龄,我知道我可以像这样制作一个不稳定的优先级队列:
I'm trying to implement a stable (first in first out) priority queue in Java. Supposing that the key is a name and the value is an age, I know I can make an unstable priority queue like this:
Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(100, ageComparator);
这几乎完成了我需要它做的所有事情,只是它在我插入(或删除它们)时不保持键值对的顺序.
This does pretty much everything that I need it to, except that it doesn't maintain order of key-value pairs as I insert them (or remove them).
我通过制作 LinkedList 找到了一种变通办法",它提供了基本上所有相同的功能,只是它不包含带有比较器选项的构造函数,而且我觉得它必须更慢,因为我通过在每个队列操作之后调用 Collections.sort()
来维护值排序.
I've found a "work around" by making a LinkedList, which offers essentially all of the same functionality, except that it doesn't include a constructor with a comparator option, and I feel that it must be slower since I maintain value ordering by calling Collections.sort()
after each queue operation.
所以我想确实有两个我感兴趣的选项.首先,我如何编辑上面的 PriorityQueue 以保持插入和删除顺序?或者第二,如何强制我的 LinkedList 选项立即使用比较器,而不必对每个操作调用排序?谢谢!
So I guess that really there are two options that I'm interested in. First, how could I edit the PriorityQueue above to maintain insertion and removal order? Or second, how could I force my LinkedList option to use a comparator immediately rather than having to call a sort on each operation? Thanks!
感谢在发布的第一条评论中提出的好问题.FIFO,我的意思是对于具有相等值的键值对,应该先提取最先放入的键值对.
Thanks for the good question in the first comment that was posted. By FIFO, I mean that for key-value pairs with equal values, the pair which is put in first should be extracted first.
推荐答案
你需要这样的东西:
import java.util.AbstractMap;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.concurrent.atomic.AtomicInteger;
public class PriorityTest {
@SuppressWarnings("serial")
private static class Entry extends AbstractMap.SimpleEntry<String, Integer> {
private final static AtomicInteger seq = new AtomicInteger(0);
final int order;
public Entry(final String _key, final Integer _value) {
super(_key, _value);
order = seq.incrementAndGet();
}
}
private static class OrderedComparator implements Comparator<Entry> {
@Override
public int compare(final Entry _e1, final Entry _e2) {
int r = _e1.getValue().compareTo(_e2.getValue());
if (r == 0)
return Integer.compare(_e1.order, _e2.order);
return r;
}
}
public static void main(String[] args) {
final PriorityQueue<Entry> pq = new PriorityQueue<Entry>(10, new OrderedComparator());
pq.add(new Entry("Jane", 22));
pq.add(new Entry("John", 15));
pq.add(new Entry("Bill", 45));
pq.add(new Entry("Bob", 22));
while(!pq.isEmpty()) {
System.out.println(pq.remove());
}
}
}
这篇关于使 Java PriorityQueue 成为稳定的优先级队列的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!