Вставить, найти мин (ключ) и удалить (в зависимости от значения) функциональность в logN с контейнерами STL?

Question

Вот интересная проблема: допустим, у нас есть набор A, для которого разрешено следующее:

• Вставка x
• Find-min x
• Удалите n-й вставленный элемент в A

Создайте структуру данных, чтобы разрешить их в логарифмическом времени.

Наиболее распространенное решение - с кучей,AFAIK, куча с ключом уменьшения (на основе значения - обычно индекса, когда элемент был добавлен) хранит таблицу со знаком Pos[1...N], означающим, что i -ое добавленное значение теперь находится в индексе Pos[i], так что он можетнайти ключ для уменьшения O (1).Кто-нибудь может это подтвердить?

Еще один вопрос - как мы решаем проблему с контейнерами STL?то есть с sets, maps или priority queues.Частичное решение, которое я нашел, состоит в том, чтобы иметь приоритетную очередь с индексами, но упорядоченными по значению этих индексов.Т.е. A[1..N] - это наши добавленные элементы в порядке вставки.pri-queue с 1..N на основе сравнения (A[i],A[j]).Теперь мы храним таблицу с удаленными индексами и проверяем, был ли удален индекс минимального значения.К сожалению, Find-min становится слегка пропорциональным без.удаленных значений.Есть альтернативные идеи?

Теперь я подумал, как сформулировать более общую проблему.Создайте структуру данных, похожую на мультикарту, с элементами <key, value>.Keys are not unique. Values are. Вставить, найти один (на основе ключа), найти (на основе значения), удалить один (на основе ключа) и удалить (на основе значения) должно быть разрешено O (logN).

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

По аналогии сстрого упорядоченный std::set (при равенстве порядка ключей по значению) с хеш-таблицей по значению, дающий итератор элементу, содержащему это значение.

Возможно с std::set и a (std :: map /)хэш-таблица), как описано Чонг Ло .

Answer 1

Вы можете использовать комбинацию из двух контейнеров для решения вашей проблемы - Вектор, в который вы добавляете каждый последовательный элемент и набор:

• Вы используете набор для выполнения find_min, в то время как
• Когда вы вставляете элемент, вы выполняете push_back в векторе и вставляете в набор
• Когда вы удаляете n-й элемент, вы видите его значение в векторе и стираете его из набора. Здесь я предполагаю, что количество элементов не изменяется после выполнения удаления n-го элемента.

Я думаю, что вы не можете решить проблему только с одним контейнером из STL. Однако есть некоторые структуры данных, которые могут решить вашу проблему:

Пропустить список - может найти минимум за постоянное время и выполнит две другие операции с амортизированной сложностью O (log (n)). Это относительно легко реализовать.

Многоуровневый вектор прост в реализации и будет выполнять find_min в постоянное время, а две другие операции в O (sqrt (n))

И, конечно, подход, который вы предлагаете - напишите свою собственную кучу, которая отслеживает, где находится n-й элемент.