Существует множество структур данных, которые реализуют интерфейс очереди приоритетов:
- Вставить: вставить элемент в структуру
- Get-Min: вернуть самый маленький элемент в структуре
- Extract-Min: удалить самый маленький элемент в структуре
Распространенными структурами данных, реализующими этот интерфейс, являются (мин) кучи .
Обычно (амортизированное) время выполнения этих операций:
- Вставьте: (иногда )O ( log n )
- Get-Min:
- Extract-Min:
Кучи Фибоначчей достигают эти запущенные разы, например. Теперь мой вопрос заключается в следующем:
Существует ли структура данных со следующим (амортизированным) временем выполнения?
- Вставить:
- Get-Min:
- Извлечение-Мин:
Если мы можем построить такую структуру за время с учетом отсортированного ввода, то, например, мы можем найти пересечения линий на предварительно отсортированных входах с помощью пересечения строго быстрее, чем если бы мы использовали «обычные» очереди с приоритетами.o ( n
data-structures
amortized-analysis
priority-queues
Алекс тен Бринк
источник
источник
Ответы:
Наша идея состоит в том, чтобы использовать резьбовые сплайны . Помимо статьи в Википедии, мы разбиваем деревья так, чтобы у каждого узла был указатель
next
на своего преемника в порядке обхода; мы также держим указательstart
на самый маленький элемент в дереве.Легко видеть, что извлечение наименьшего элемента возможно в (наихудшем случае) времени : просто следуйте указателю, уберите минимум и измените указатель на минимум . У минимума никогда не может быть оставленного ребенка; если у него есть правильный ребенок, мы помещаем его в минимальное место на дереве. Мы не выполняем операцию splay, обычно это делают splay-деревья. Результатом является дерево поиска, которое все еще достаточно сбалансировано: поскольку мы удаляем только узлы на левом фланге, мы знаем, что когда число узлов (в затронутом поддереве) уменьшается примерно до половины исходного числа из-за удалений, ) высота дерева уменьшается на единицу.O(1)
start
next
Вставки возможны в амортизированное время; зигзагообразные (и не очень) операции здесь также хорошо сбалансируют дерево.O(logn)
Это грубый набросок в лучшем случае. Авторы обращаются к Ф. Вайнбергу, который озадачился вопросом со мной и нашим советником М. Небелем, который упомянул о кустарниках, о единственном варианте дерева, который мы не пробовали.
источник
Амортизированное время
Простые реализации очереди с приоритетами (например, любой сбалансированный BST или стандартная двоичная минимальная куча) могут достичь этих (амортизированных) времен выполнения, просто взимая стоимость Extract-Min для вставки и поддерживая указатель на минимальный элемент. Например, у вас может быть потенциальная функция . Затем вставка нового элемента увеличивает потенциал на , поэтому амортизированная стоимость вставки по-прежнему равна , но Extract-Min () уменьшает потенциал на , и таким образом, амортизированная стоимость составляет всего .O ( log n ) O ( log n ) Ω ( log n ) O ( 1 )cnlogn O(logn) O(logn) Ω(logn) O(1)
Худший случай
Вы можете использовать существующую структуру данных в литературе: деревья поиска пальцами и просто поддерживать указатель на минимальный элемент. См. Этот обзор для обзора, а также статью Levcopoulos and Overmars 1988 года для реализуемой версии, которая соответствует вашим потребностям.
источник
2-4 дерева имеют амортизированные модификации в известных местах. То есть, если у вас есть указатель на какое-то место в дереве, вы можете удалить или добавить элемент там за амортизированное время.O ( 1 )O(1) O(1)
Таким образом, вы можете просто сохранить указатель на минимальный элемент и корневой узел в дереве 2-4. Вставки должны проходить через корневой узел. Обновление указателя до минимума является тривиальным после deleteMin, а deleteMins - (амортизированное) время.O(1)
Интересное примечание: красно-чёрные деревья - это просто способ посмотреть на 2-4 дерева. Разработчики стандарта C ++ 98 ожидали, что разработчики библиотек предоставят контейнер на основе красно-черного дерева, а в стандарте указано, что вставка и удаление должны иметь время амортизации в известных местах (которые они называют «итераторами»). ). Тем не менее, это на самом деле намного сложнее для красно-черных деревьев, чем для 2-4 деревьев, поскольку требует ленивой разметки узлов, которые необходимо перекрасить. Насколько мне известно, никакие реализации стандартной библиотеки C ++ 98 не удовлетворяли этому конкретному требованию.O(1)
источник
По запросу, вот структура, которую я нашел после того, как сформулировал вопрос:
Основная идея состоит в том, чтобы использовать резьбовое дерево козла отпущения вместе с указателем на минимум (и, на всякий случай, максимум). Более простой альтернативой многопоточности является поддержание указателей предшественника и преемника в каждом узле (что эквивалентно, проще, но имеет больше накладных расходов). Я пришел, чтобы назвать это кучей козла отпущения , просто чтобы дать ей какое-то имя.
Именно эта базовая структура дает вам следующие операции:
При анализе деревьев козла отпущения, накладные расходы на удаление анализируются как , но на самом деле анализ дает накладные расходы на баланс (который игнорируется в статье поскольку они также подсчитывают время, необходимое для поиска узла, который должен быть удален). Итак, если у нас есть указатель на узел, мы можем удалить его за постоянное время (вы можете сделать это в многопоточном бинарном дереве поиска за время) и объединить с накладные расходы на балансировку, это дает время удаления:O ( 1 ) O ( log n ) O ( 1 ) O ( 1 ) O ( 1 )O(logn) O(1) O(logn) O(1) O(1) O(1)
Сочетая это:
Вы можете сделать немного больше с указателями: например, нетрудно поддерживать указатель на медиану или некоторую другую статистику порядка, поэтому вы можете поддерживать постоянное количество таких указателей, если они вам нужны.
Некоторые другие вещи:
И, наконец, я почти уверен, что вы можете поддерживать эти операции, но мне нужно немного подумать об этом, прежде чем точно знать это:
источник
Мягкая куча - это тонкая модификация биномиальной очереди. Структура данных является приблизительной с параметром ошибки . Он поддерживает вставку, удаление, объединение и findmin. Амортизируется сложность каждой операции , для вставки , которая принимает , за исключением время. Новизна мягкой кучи заключается в преодолении логарифмической границы сложности кучи в модели, основанной на сравнении. Чтобы преодолеть теоретико-информационный барьер, энтропия структуры данных снижается путем искусственного повышения значений некоторых ключей. Это называется повреждением ключей. Структура данных полностью основана на указателях (без массивов и числовых предположений) и является оптимальной для любого значенияϵ O(1) log(1/ϵ) ϵ в модели на основе сравнения.
Приложения мягкой кучи включают в себя вычисление минимального связующего дерева для графа, динамическое ведение процентилей и статистику линейного временного порядка. Это также может быть использовано для приближенных вычислений, таких как приближенная сортировка, где ранг элемента никогда не отличается более чем на от истинного ранга.ϵn
Оригинальную, ясную и хорошо написанную статью см. В статье Бернарда Шазеля «Мягкая куча: очередь с приблизительным приоритетом с оптимальным коэффициентом ошибок», журнал ACM, 47 (6), стр. 1012-1027, 2000 . Для альтернативной реализации и анализа, который утверждает, что является более простым и интуитивно понятным из SODA'09, см. Kaplan H. & Zwick U., Более простая реализация и анализ мягких куч Хазелля, 2009 .
источник
Хорошо, наконец-то у вас сложность, которую вы искали, и, что лучше, я нашел ее в литературе:
Наихудшая Сложность
Удалить :O(1)
Delete-min :O(1)
Find-min :O(1)
Вставьте :O(log n)
Ссылка
Бродал, Герт Штелтинг. «Быстрые приоритетные очереди». В материалах 4-го международного семинара по алгоритмам и структурам данных, 282–290. WADS '95. Лондон, Великобритания, Великобритания: Springer-Verlag, 1995.
[3]
: Дитц, Пол Ф. и Раджив Раман. «Дерево поиска пальца с постоянным временем обновления». Письма обработки информации 52, нет. 3 (1994): 147 - 154.Хотя для этого используется модель вычисления RAM :
Совсем недавно была предложена модель вычислительного решения Pointer-Machine
[1]
.[1]
: Бродал, Герт Stølting, Джордж Lagogiannis, Christos Makris, Атанашес Тсакалидис и Костас Tsichlas. «Оптимальные деревья поиска пальцев в указателе». J. Comput. Сист. Sci. 67, нет. 2 (сентябрь 2003 г.): 381–418.источник
Подходя к этой проблеме, поддерживая две структуры данных: массив и двоичное дерево.
null
delete_at(idx)
1 Патраску, Михай и Эрик Д. Демейн. «Логарифмические нижние границы в модели клеточного зонда». SIAM J. Comput. 35, нет 4 (апрель 2006 г.): 932–963. DOI: 10.1137 / S0097539705447256.
источник
Find-min в с ожидаемым временем обновленияO(1) O(log log n−−−−−−−√)
См. Статью 2007 года: Эквивалентность между приоритетными очередями и сортировкой Миккеля Торупа.
Примечание: он ссылается на статью 2002 года Хана и Торапа: Целочисленная сортировка в Ожидаемое время и линейное пространствоO(n log log n−−−−−−−√) .
источник
Анализ
Вставить :o(n log log n)
Поиск :o(log log n)
Удалить :O(1)
Пробел :O(n)
Get-Min :O(1)
Извлечение-Мин :O(1)
Реализация
[1]: Андерссон, Арне и Кристер Маттссон. «Динамический интерполяционный поиск за O (log log n) Time». В «Автоматах, языках и программировании» под редакцией Анджея Лингаса, Рольфа Карлссона и Сванте Карлссона, 700: 15–27. Конспект лекций в области компьютерных наук. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58 .
источник