java - 什么结构最适合 "Get first X elements with best priority"？

Question

我有很多具有 int 优先级的元素。元素的优先级是可变的。

操作计数getFirstPriorityElements(int count) - n
操作计数 updatePriorityOfElement(Object o, intpriority) - n

我应该使用什么最佳性能结构来获取具有最佳优先级的前 X 个元素？

Answer 1

如果您想拥有恒定的优先级，则 PriorityQueue 或 TreeSet 会适合您(队列是如果您想弹出元素，集合 - 如果您想要保留它们)。

但是，随着优先级的变化，您必须在每次更改时对集合重新排序。或者更好 - 在每次迭代之前。不过，这应该是同步的。

因此，创建一个使用自定义Comparator 的集合，并在每次调用iterator() 时重新排序其元素。例如，您可以扩展 TreeSet 并重写 iterator() 方法。然后调用 next() n 次。