CODEWITHSUNDEEP
scalascala-2.8priority-queuedeque
Łukasz Lew
Łukasz Lew

Reputation: 50298

Is it possible to have two priority queues "in sync" in Scala?

I have a set of objects with two kinds of priorities. I can create two PriorityQueues ordered by each of them. The problem is that when I dequeue element from one of them it will obviously not disappear from the other one.

Is it possible to create 2 queues "in sync", so that when element is removed from one then it will be removed from the other?

Upvotes: 1

Views: 217

Answers (2)

Raphael
Raphael

Reputation: 10559

If you do not need logarithmic operations, just use double linked list as queues. They do not guarentee FIFO but provide what you need.

You can easily wrap two of those in one class.

Upvotes: 0

axel22
axel22

Reputation: 32335

This warrants a special kind of a data structure. The standard "binary heap under the hood" priority queue available in the standard library cannot do the trick, because it doesn't know "where" in the other binary heap the required element is.

A similar problem happens when you try to implement Dijkstra's algorithm or A*. The trick that works there is to use 2 ordered trees as if they were queues - you can pop the first element, and you can then search for it in the other tree.

Upvotes: 3

Related Questions