Мне нужна такая структура данных, которая бы позволяла делать эффективно следующие две вещи. Эффективно в смысле, как минимум, со сложностью O(log n) относительно количества данных.
Первое. Это должна быть очередь с приоритетами, так чтобы я мог эффективно извлечь элемент с минимальным ключом. Для ключей есть отношение упорядоченности.
Второе. Эта структура должна позволять эффективно удалять заданный элемент по значению. Для определенности допустим, что существует отношение упорядоченности и для значений элементов, т.е. можно строить двоичные деревья со сравнением.
Сейчас есть хип (императивный или чистый функциональный - без разницы). На основе его легко строится эффективная очередь с приоритетами. Но вот, если вводить удаление полным перебором, то там сразу возникает сложность O(n), что совсем не комильфо.
Может быть, есть более эффективный способ? Что-то ничего умного в голову не лезет.
