将Java PriorityQueue变成稳定的优先级队列
我试图在Java中实现一个稳定的(先到先出)优先级队列。假设键是一个名称，值是一个年龄，我知道我可以像这样做一个不稳定的优先级队列：
Queue<Map.Entry<String, Integer>> pq = new PriorityQueue<Map.Entry<String, Integer>>(100, ageComparator);这几乎完成了我需要它做的所有事情，除了当我插入它们(或者删除它们)时，它没有保持键值对的顺序。
我通过创建一个LinkedList找到了一个“工作”，它基本上提供了所有相同的功能，但它不包括带有比较器选项的构造函数，而且我觉得它必须慢一些，因为我在每次队列操作之后调用Collections.sort()来维护值排序。
所以我想我有两种选择感兴趣。首先，如何编辑上面的PriorityQueue以保持插入和删除顺序？或者第二，我如何强制我的LinkedList选项立即使用一个比较器，而不是对每个操作调用一个排序？谢谢!
编辑：
谢谢你在第一条评论中提出的好问题。所谓FIFO，我的意思是，对于等值的键值对，应该先提取放在第一位的对。
回答 3
Stack Overflow用户
发布于 2014-03-29 10:26:00
你需要这样的东西：
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());
}
}
}Stack Overflow用户
发布于 2016-12-04 11:09:53
基于Keap的PriorityQueue自然是稳定的。它是用Kotlin编写的，因此可以在Java代码中替换java.util.PriorityQueue。
Stack Overflow用户
发布于 2020-11-18 12:55:55
基于多个列表和TreeMap的非常简单的实现，我今天已经完成了一些任务：
import javax.annotation.Nonnull;
import java.util.*;
import java.util.Map.Entry;
import java.util.function.Function;
public class PriorityFifo<E> {
protected TreeMap<Integer, LinkedList<E>> storage = new TreeMap<>();
public void push(E element, int priority) {
storage.computeIfAbsent(priority, it -> new LinkedList<>()).addLast(element);
}
public Optional<E> poll() {
return doWithNextElement(LinkedList::pollFirst);
}
public Optional<E> peek() {
return doWithNextElement(LinkedList::getFirst);
}
protected Optional<E> doWithNextElement(@Nonnull Function<LinkedList<E>, E> f) {
Entry<Integer, LinkedList<E>> entry = storage.firstEntry();
if (entry==null)
return Optional.empty();
LinkedList<E> list = entry.getValue();
E element = f.apply(list);
if (list.isEmpty())
storage.remove(entry.getKey());
return Optional.of(Objects.requireNonNull(element));
}
}没有用于元素的比较器，但是TreeMap对队列在内部使用。我的例子是，我只有几个优先级，但是有很多元素，所以它应该比使用元素比较更快。
https://stackoverflow.com/questions/21617098
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号