java - 具有不断变化的键值的优先级队列

Question

我必须模拟一个优先级队列。队列中的 key 会定期更改。队列必须能够:添加元素和删除元素。最好的方法是什么(具有最好的复杂性)？什么是最好的数据结构？

Answer 1

我推荐以下两种方法之一:

1. (高级)使用 Java 的 PriorityQueue 实现所使用的堆数据结构。当元素的优先级发生变化时，您需要对堆执行“向上筛选”和“向下筛选”操作，以确保堆顶仍然代表优先级队列中最高的元素。向上筛选和向下筛选是构成 heapsort 的一部分的操作.
2. (简单)使用无序列表作为优先队列。这意味着可以使用 O(1) 访问时间插入元素，并且调整元素的优先级不涉及对数据结构的任何操作。然而，权衡是访问最高优先级的元素是 O(n)。