Эффективная очередь приоритетов с несколькими ключами?

Question

У меня возникла проблема, которую я вполне уверен, что кто-то уже встретился и решил, но я просто не могу найти решение.

У меня есть несколько объектов, каждый объект имеет несколько ключей. Скажи:

• (1, 2): а
• (3, 3): В
• (4, 4): С
• (5, 1): D

Мне нужна структура данных с «приоритетной очередью», которая позволяет мне эффективно возвращать объекты по приоритету для каждого из ключей отдельно. Например, если я верну их по первому ключу, я бы получил (A, B, C, D), а вторым ключом я получил бы (D, A, B, C). Тем не менее, мне также нужно иметь возможность смешать. Например, возвращаясь по клавишам в качестве альтернативы, начиная с первого, давая мне (A, D, B, C). Очевидно, что всплытие объекта первым ключом должно удалить второй ключ.

Наивное решение - это данные при изменении ключа поиска, но это слишком медленно для моих целей. Другой альтернативой является использование кучи и перемещение другой кучи для каждого объекта, но, насколько я могу судить, это тоже медленно. Есть ли алгоритм для эффективной очереди приоритетов, который позволяет мне удалять объекты несколькими разными ключами?

Если есть реализация для python, это было бы очень приятно, но алгоритм был бы очень хорошим началом.

Answer 1

Я думаю, что лучший подход - иметь отдельную кучу для каждой клавиши. Когда вы удаляете первый элемент одной кучи, вы не можете эффективно удалить его из других куч, но вы можете «пометить» его каким-либо образом (например, путем его изменения или добавив его в set, если это хешируется), поэтому что его можно игнорировать, если он в конечном итоге снова появится в другом месте.

Это может немного раздуть ваши кучи, поскольку оно будет поддерживать бесполезные ценности вокруг, но я думаю, что это все равно будет намного быстрее, чем удаление и повторное воспроизведение.