Возможно ли иметь две приоритетные очереди "в синхронизации" в Scala?

Question

У меня есть набор объектов с двумя видами приоритетов.Я могу создать две PriorityQueues по заказу каждого из них.Проблема в том, что когда я снимаю элемент с одного из них, он, очевидно, не исчезнет с другого.

Можно ли создать 2 очереди "в синхронизации", чтобы при удалении элемента из одного онбудут удалены из другого?

Answer 1

Это гарантирует особый вид структуры данных. Стандартная очередь с приоритетами «двоичная куча», доступная в стандартной библиотеке, не может справиться с задачей, поскольку она не знает «где» в другой двоичной куче необходимый элемент.

Аналогичная проблема возникает, когда вы пытаетесь реализовать алгоритм Дейкстры или A *. Уловка, которая работает там, состоит в том, чтобы использовать 2 упорядоченных дерева, как если бы они были очередями - вы можете открыть первый элемент, а затем найти его в другом дереве.

Answer 2

Если вам не нужны логарифмические операции, просто используйте двойной связанный список в качестве очередей. Они не гарантируют FIFO, но предоставляют то, что вам нужно.

Вы можете легко обернуть два из них в одном классе.