具有高效删除(...)(或更新)的Java优先级队列

Question

我正在开发一个事件驱动的模拟器，我的事件都在 java.util.PriorityQueue 中。问题是事件在运行时被重新安排了很多次，并且由于在库存 PriorityQueue 中没有更新优先级，我删除了元素并使用新的优先级重新插入它们。

这行得通，但性能(太)差了，而且扩展性不好。 JVisualVM 的分析器告诉我 99% 的时间都浪费在了 pq.delete(...) 上。

是否有一种 PQ 的实现可以有效地更新优先级，或者至少有一个其中 delete(...) 比 stock 的 O(N) 更有效的 PQ？

我尝试了 Fibonacci 堆，它在特定点上工作得更快，但也不能很好地扩展。

Answer 1

这是一个队列解决方案:不要从队列中删除，而是维护一个单独的队列。每当您需要打乱优先级时，您只需形成一个新队列并用它替换原来的队列。

为避免潜在的并发问题，您应该在某个时间点阻止读取器/写入器以重新分配队列。