是否有可能在Scala中“同步”两个优先级队列？

Question

我有一组对象有两种优先级。 我可以创建两个由他们每个排序的PriorityQueue。 问题是，当我从其中一个元素中取出元素时，它显然不会从另一个元素中消失。

是否有可能创建2个“同步”队列，以便当从一个元素被删除时，它将被从另一个删除？

Answer 1

这保证了一种特殊的数据结构。标准库中可用的标准“引擎盖下的二进制堆”优先级队列无法做到这一点，因为它不知道其他二进制堆中的“哪里”是所需的元素。

当您尝试实现Dijkstra算法或A *时会出现类似问题。在那里工作的技巧是使用2个有序的树，就好像它们是队列一样 - 你可以弹出第一个元素，然后你可以在另一个树中搜索它。

Answer 2

如果您不需要对数运算，只需使用double linked list作为队列。他们不保证先入先出，但提供你所需要的。

你可以很容易地将其中的两个包装在一个类中。