Нужна структура данных

Question

Подумав, я пришел к выводу, что мне нужна структура данных, которая поддерживает:

• Вставить
• Удалить
• Найти
• Удалить минимум

конечно, я хочу реализовать это как можно лучше.

Я думаю, что самообалансирующееся дерево двоичного поиска будет выполнять A-D в O (log (n)) (наихудший случай). Возможно, это можно как-то улучшить, так что A-C будет в O (log (n)), а D (что, я думаю, будет чаще) будет работать в O (1).

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

(примечание: я считаю, что A и D будут гораздо чаще, чем B и C)

Answer 1

То, что вы описываете, это приоритетная очередь , дополненная операцией «найти».

Обычно она реализуется в терминах мин-куча .Все перечисленные вами операции, кроме «find», выполняются в O (log n ), и это, в частности, наиболее эффективная общая структура данных для этого задания.Важно отметить, что это особый случай двоичного дерева, которое может быть реализовано гораздо более эффективно, чем обычное двоичное дерево поиска, как с точки зрения потребления памяти, так и производительности (та же асимптотическая производительность, но гораздо лучшие постоянные факторы).*

К сожалению, «find» все еще занимает O ( n ).

Он реализован в Java в классе PriorityQueue.

Answer 2

Это должно быть какое-то отсортированное сбалансированное дерево.Маловероятно, что какое-либо дерево будет лучше подходить для минимального удаления, так как оно все равно потребует повторной балансировки.Все запрошенные вами операции будут O (log (n)).Красно-черные деревья легко доступны на C ++ и Java.