我必须模拟一个优先级队列。队列中的 key 会定期更改。队列必须能够:添加元素和删除元素。最好的方法是什么(具有最好的复杂性)?什么是最好的数据结构?
最佳答案
我推荐以下两种方法之一:
- (高级)使用 Java 的 PriorityQueue 实现所使用的堆数据结构。当元素的优先级发生变化时,您需要对堆执行“向上筛选”和“向下筛选”操作,以确保堆顶仍然代表优先级队列中最高的元素。向上筛选和向下筛选是构成 heapsort 的一部分的操作.
- (简单)使用无序列表作为优先队列。这意味着可以使用 O(1) 访问时间插入元素,并且调整元素的优先级不涉及对数据结构的任何操作。然而,权衡是访问最高优先级的元素是 O(n)。
关于java - 具有不断变化的键值的优先级队列,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7905034/