Эквивалентность между очередями с приоритетами и сортировкой: различия между версиями

1. (Детерминированный) время обновления O(log log n) при помощи алгоритма сортировки из [9].

2. (Рандомизированный) ожидаемое время обновления <math>O(\sqrt{log \; log \; n})</math> при помощи алгоритма сортировки из [10].

3. (Рандомизированный с выполнением операции decrease-key за время O(1)) ожидаемое время обновления <math>O \Big( (log \; n)^{\frac{1}{2 - \epsilon}} \Big)</math> для слов длиной, больше или равной log n, и любого константного <math>\epsilon > 0</math> при помощи алгоритма сортировки из [3].

1. (Детерминированный для стандартного алгоритма класса сложности <math>AC^0</math>) время обновления <math>O((log \; log \; n)^{1 + \epsilon})</math> для любого константного <math>\epsilon > 0</math> 0 при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [10].

2. (Рандомизированный для стандартного алгоритма <math>AC^0</math>) ожидаемое время обновления O(log log n) при помощи стандартного алгоритма сортировки целых чисел класса <math>AC^0</math> из работы [16].

3. (Строки из l слов) ожидаемое время обновления O(l + log log n) для детерминированного и <math>O(l + \sqrt{log \; log \; n})</math> – для рандомизированного случая при помощи алгоритма сортировки строк из [10].

Структура данных состоит из двух основных компонентов: отсортированного списка ключей и множества буферов обновления. Список ключей разбит на два небольших сегмента, каждый из которых поддерживается в виде атомарной кучи, обеспечивающей константное время выполнения операций обновления и поиска на этом сегменте. Каждый буфер обновления имеет разную емкость объем и поддерживает обновления (вставка / удаление) со значениями ключей в разных диапазонах. Буферы меньшей емкости предназначены для обновления ключей меньшей величины. Атомарная куча используется для определения за константное время того, какой буфер обновления содержит новое обновление. Когда буфер обновления соберет достаточно обновлений, они вначале проходят этап сортировки, а затем – этап слияния. На этапе слияния каждое обновление применяется к соответствующему сегменту списка ключей, а также фиксируются инварианты размеров сегментов и диапазонов буферов обновления. Эти этапы выполняются не немедленно, а в фиксированные временные отрезки в рамках общего периода времени. Буфер обновления продолжает принимать новые обновления, при этом некоторые ранее принятые им обновления все еще могут находиться на этапе сортировки, а некоторые более поздние – на этапе слияния. При получении каждого нового обновления на связанном с ним этапе сортировки на него тратится S(n) времени, а на этапе слияния – O(1) времени. Эта стратегия позволяет доводить этапы сортировки и слияния до завершения к моменту очередного заполнения буфера обновления, обеспечивая плавность прохождения обновлениями нужных этапов и сохраняя время обновления S(n) + O(1) в худшем случае. Кроме того, ограничения на размер и емкость гарантируют, что даже самый маленький ключ в структуре данных доступен за время O(1). Далее изложим эту технологию более подробно.

'''Буферы обновления''': базовые сегменты отделяются друг от друга ''базовыми разделителями'', из которых O(log n) выбираются в качестве ''верхних разделителей'', так что количество ключей в базовом списке под i-м верхним разделителем <math>s_i</math> (i > 0) составляет <math>\Theta (4^i(log \; n)^2)</math>. Эти разделители располагаются а атомарной куче. По мере изменений базового списка верхние разделители перемещаются по необходимости с тем, чтобы сохранить их экспоненциальное распределение.

С каждым верхним разделителем <math>s_i</math>, i > 1, ассоциированы три буфера: ''входной буфер'', ''буфер сортировки'' и ''буфер слияния'', каждый емкостью в <math>4^i</math> ключа. Верхний разделитель <math>s_i</math> работает по циклу, состоящему из <math>4^i</math> шагов. В начале цикла входной буфер пуст, буфер сортировки содержит не более <math>4^i</math> обновлений, а буфер слияния – отсортированный список из не более чем <math>4^i</math> обновлений. На каждом этапе можно принять обновление во входной буфер, потратить <math>O(4^i) = S(n)</math> времени на буфер сортировки и O(1) времени на слияние отсортированного списка в буфере слияния, в то время как <math>O(4^i)</math> базовых разделителя находятся в интервале <math>[s_{i - 2}, s_{i + 1})</math> (предполагая <math>s_0 = 0, s_{-1} = - \infty)</math>, и сканирование на наличие нового <math>s_i</math> среди них. Данная реализация гарантирует, что все ключи в буферах разделителя <math>s_i</math> находятся в интервале <math>[s_{i - 2}, s_{i + 1})</math>. Таким образом, после <math>4^i</math> таких шагов цикла отсортированный список корректно слит с базовым списком, найдено новое значение <math>s_i</math> и создан новый отсортированный список. Затем буфер сортировки принимает на себя роль буфера слияния, входной буфер становится буфером сортировки, а пустой буфер слияния становится новым входным буфером.

Операция find-min возвращает минимальный элемент базового списка, доступный за время O(1).

Доказательства эквивалентности, приведенные в [15], могут использоваться для перевода известных результатов сортировки в новые результаты для очередей с приоритетами для целых чисел и строк в различных вычислительных моделях (см. раздел. «Основные результаты»). Эти результате также можно рассматривать как новые способы доказательства нижних границ для сортировки посредством очередей с приоритетами.

Новая очередь с приоритетами на RAM-машине, соответствующая приведенным в теореме 1 границам и поддерживающая операцию decrease-key за время O(1), представлена в работе [17]. Это построение сочетает экспоненциальные деревья поиска Андерссона [2] и очереди с приоритетами, упомянутые в теореме 1. Редукция в теореме 1 также использована в [12] для разработки адаптивного алгоритма сортировки целых чисел для пословной RAM-машины. Редукции из очередей с приоритетами, допускающих слияние, к сортировке, представленные в [11], используют редукции из очередей с приоритетами, не допускающих слияния, к сортировке, представленные в [15].

Как упоминалось выше, комбинаторная редукция для машин с указателями, приведенная в теореме 2, является более слабой, чем редукция для пословных RAM-машин. Например, для гипотетического алгоритма сортировки с линейным временем выполнения теорема 1 предлагает очередь с приоритетами с временем обновления O(1), а теорема Theorem – с временем обновления <math>2^{O(log^* \; n)}</math>. Остается открытым вопрос о том, можно ли устранить или уменьшить этот разрыв.