Я мечтал о структуре данных, она существует?

27

Мне не удалось найти эту структуру данных, но я не эксперт в этой области.

Структура реализует множество и представляет собой массив сопоставимых элементов с инвариантом. Инвариант следующий (определяется рекурсивно):

Массив длиной 1 является массивом слияния.

Массив длиной 2 ^ n (для n> 0) является массивом слияния, если:

  • первая половина является массивом слияния, а вторая половина пуста или
  • первый массив заполнен и отсортирован, а вторая половина является массивом слияния.

Обратите внимание, что если массив заполнен, он сортируется.

Чтобы вставить элемент, у нас есть два случая:

  • Если первая половина не заполнена, вставьте рекурсивно в первую половину.
  • Если первая половина заполнена, вставьте рекурсивно во вторую половину.
  • После рекурсивного шага, если весь массив заполнен, объедините половинки (которые отсортированы) и измените его размер в два раза по сравнению с его первоначальной длиной.

Чтобы найти элемент, выполните рекурс в обеих половинах, используя двоичный поиск, когда массив заполнен. (Это должно быть эффективно, поскольку существует не более восходящих фрагментов).O(log(n))

Структура может рассматриваться как статическая версия сортировки слиянием.

Не ясно, что нужно сделать, чтобы стереть элемент.

Изменить: после улучшения моего понимания структуры.

pbaren
источник
5
Вы определили это, поэтому оно существует. Я думаю, что вы должны сгладить некоторые моменты, хотя. Во-первых, меня смущает инвариант № 2, который, кажется, не относится к промежуточным состояниям, как вы их описываете. Во-вторых, что вы делаете, когда элементы удалены?
Рафаэль
7
Вы снились вверх структура данных, а не снились его ...
Андрей Bauer
@Raphael Спасибо за ваши комментарии, я улучшил определение, следуя вашим мыслям. Я не думал об алгоритме удаления, я просто хотел проверить, есть ли эта структура в литературе, прежде чем уделять ей больше времени (и ничего не смог найти в Google). В первом предложении вы можете определить Бога, но существует ли он? :)
pbaren
@ Андрей Спасибо, английский не мой родной язык. (Думаю, это тоже не твое :)
pbaren
3
@Andrej: ОП изначально был «мечтал с », что почти наверняка не то , что имелось в виду. Я изменил его на «из» вместо «вверх». Оба грамматически верны, но оба также меняют смысл. "Of" был более интересным вариантом звучания ...
Андраш Саламон

Ответы:

31

ABABO(logn)n), но увеличивает пространство только постоянным фактором. Да, это может быть деамортизировано, благодаря Overmars и van Leeuwen, но вы действительно не хотите делать это, если вам не нужно.

Эти заметки охватывают основы.

Мешки с заброшенным кэшем - мутантное потомство деревьев Бентли-Сакс и Ван-Эмде-Боаса на стероидах.

Jeffε
источник
4
Это прекрасно написанные и иллюстрированные заметки, и я много раз использовал их в качестве ссылки. Спасибо, что сделали их доступными!
Jbapple
Я вижу, как челночные деревья (из первой половины статьи, представляющей массивы предпросмотра кэша) связаны с деревьями vEB, но какова связь между COLA и деревьями vEB?
Jbapple
2
Спасибо, этот материал кажется очень интересным обобщением идеи. Я всегда думал, что структуры данных - это замороженные алгоритмы, которые вы можете запускать шаг за шагом, но я никогда не находил полезной формализации этой интуиции.
Пбарен
Первая ссылка сработала у кого-то еще?
AT
Да, я только что попробовал. (К сожалению, он идет в платный Elsevier; извините!)
Джефф