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

Ключевые слова и синонимы

Куча

Постановка задачи

Очередь с приоритетами представляет собой абстрактную структуру данных, поддерживающую множество из Q элементов, каждому из которых присвоено значение, называемое ключом, а также следующий набор операций [4, 7].

insert(Q, x, k): вставка элемента x с ключом k в Q.

find-min(Q): возврат элемента Q с минимальным ключом; Q не изменяется.

delete(Q, x, k): удаление элемента x с ключом k из Q.

Помимо этого, нередко поддерживаются также следующие операции.

delete-min(Q): удаление элемента с минимальным ключом из Q и возврат измененного множества.

decrease-key(Q, x, k): уменьшение текущего ключа k' элемента x до k, предполагая, что k < k'.

meld([math]\displaystyle{ Q_1, Q_2 }[/math]): на входе очереди с приоритетами [math]\displaystyle{ Q_1 }[/math] и [math]\displaystyle{ Q_2 }[/math], на выходе – очередь с приоритетом [math]\displaystyle{ Q_1 \cup Q_2 }[/math].

Заметим, что операция delete-min может быть реализована как комбинация find-min и последующей delete, decrease-key – как delete с последующей insert, а meld – как серия find-min, delete и insert. Однако существуют и более эффективные реализации decrease-key и meld [4, 7].

Очереди с приоритетами широко применяются на практике, в том числе для событийного моделирования, планирования заданий на совместно используемом компьютере, а также вычисления кратчайших путей, минимальных остовных лесов, паросочетания с минимальной стоимостью, оптимального ветвления и т. п. [4, 7].

Очередь с приоритетами может тривиально использоваться для сортировки; для этого вначале необходимо вставить все подлежащие сортировке ключи в очередь и затем последовательно извлекать текущий минимальный ключ. Основным вкладом работы [15] является редукция, демонстрирующая, что обратное также верно. Из результатов работы [15] следует, что очереди с приоритетами вычислительно эквивалентны сортировке, а именно, что асимптотически стоимость сортировки в пересчете на ключ равна времени обновления очереди с приоритетами.

Аналогичный [15] результат, представленный в работе [14], представляет собой очереди с монотонными приоритетами (что означает, что извлекаемые минимальные значения являются неубывающими) с амортизированными временными границами. Напротив, очереди с приоритетами общего вида с границами для худшего случая были построены в [15].

Помимо установления эквивалентности между очередями с приоритетами и сортировкой, редукции в работе [15] также используются для преобразования нескольких известных результатов для сортировки в новые результаты для очередей с приоритетами.

Контекст и история

Нижеследующая информация будет полезной для более полного понимания результатов, приведенных в разделе «Основные результаты».

• Стандартная пословная RAM-машина моделирует ход выполнения программы, написанной на стандартном языке программирования, таком как С. Помимо прямой и косвенной адресации и условных переходов, программа может содержать функции (например, сложение и умножение), выполняемые над константным количеством слов. Память разделена на два слова с линейной адресацией, начинающейся с 0. Время выполнения программы равно количеству выполненных команд, а объем памяти – номеру максимального использованного адреса. Длина слова представляет собой машинно-зависимый параметр, достаточно большой для хранения ключа, и является по меньшей мере логарифмической относительно количества входных ключей, что обеспечивает возможность их адресации.

• Машина с указателями аналогична пословной RAM-машине за тем исключением, что с адресами нельзя производить какие-либо действия.

• Класс сложности [math]\displaystyle{ AC^0 }[/math] включает схемы константной глубины с неограниченным коэффициентом разветвления по входу [18]. Под стандартными операциями [math]\displaystyle{ AC^0 }[/math] понимаются операции, доступные в C, такие, что функции над словами принадлежат к [math]\displaystyle{ AC^0 }[/math]. К примеру, в их число входит сложение, но не умножение.

• Целочисленные ключи ссылаются на неотрицательные целые числа. Если же входные ключи представляют собой целые числа со знаком, корректный порядок ключей можно получить в результате переключения битов, содержащих знаки, и интерпретации их как беззнаковых целых чисел. Аналогичные действия можно произвести для чисел с плавающей запятой и дробных чисел [14].

• Атомарные кучи Фредмана и Уилларда [6] использовались в одной из редукций в работе [15]. Такие кучи способны поддерживать операции обновления и поиска в множествах из [math]\displaystyle{ O(log^2 \; n) }[/math] ключей за время O(1) в худшем случае [19]. Однако атомарные кучи используют операции умножения, не принадлежащие к [math]\displaystyle{ AC^0 }[/math].

Основные результаты

Основными результатами являются две редукции из очередей с приоритетами к сортировке. Более сильная из этих редукций, изложенная в теореме 1, касается целочисленных очередей с приоритетами, выполняющихся на стандартной пословной RAM-машине.

Теорема 1. Если для некоторой неубывающей функции S до n целочисленных ключей могут быть отсортированы за время S(n) на ключ, целочисленная очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления, т. е. вставки и удаления, за время S(n) + O(1). Здесь n равно текущему количеству ключей в очереди. Редукция использует линейный объем памяти и выполняется на стандартной пословной RAM-машине, на которой каждый целочисленный ключ хранится в одном слове.

Вышеприведенная редукция задает новые границы для линейных требований к объему памяти для целочисленных очередей с приоритетами, улучшая предыдущие границы, представленные в работах [8, 14] и [5], соответственно.

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

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

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

Редукция из теоремы 1 использует атомарные кучи [6], которые мало того что очень сложны сами по себе, но к тому же используют операции, не входящие в [math]\displaystyle{ AC^0 }[/math]. Следующая, несколько более слабая рекурсивная редукция, не ограничивающая область определения ключей, является полностью комбинаторной.

Теорема 2. Пусть дана программа сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами может быть реализована с поддержкой операции find-min за константное время и операций обновления – за время T(n), где n – текущее количество ключей в очереди, а T(n) удовлетворяет следующему условию рекуррентности:

[math]\displaystyle{ T(n) = O(S(n) + T(log^2 \; n)) }[/math]

Редукция выполняется на машине с указателями с использованием линейного объема памяти и только стандартными операциями из [math]\displaystyle{ AC^0 }[/math]. Обращения к значениям ключей производятся только программой сортировки.

Данная редукция обеспечивает следующие новые границы для очередей с приоритетами, не поддерживаемые теоремой 1, причем первые две позиции улучшают предыдущие границы, представленные в работах [13] и [16], соответственно.

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

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

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

Редукция в теореме 1

Пусть дана процедура сортировки, выполняющая сортировку до n ключей за время S(n) на ключ. Очередь с приоритетами строится следующим образом.

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

Отсортированный список ключей: отсортированный список содержит большинство ключей в структуре данных, в том числе минимальный ключ, и называется базовым списком. Этот список разбит на базовые сегменты, каждый из которых содержит [math]\displaystyle{ \Theta((log \; n)^2) }[/math] ключей. Ключи в каждом сегменте поддерживаются в виде атомарной кучи, так что если становится известно, что новое обновление должно быть применено к конкретному сегменту, оно может быть применено за время O(1). Если базовый сегмент становится слишком большим или слишком маленьким, он разбивается на две части либо объединяется со смежным сегментом.

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

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

Обработка обновлений: при получении нового ключа обновления k (вставка или удаление) атомарная куча с верхними разделителями позволяет за время O(1) найти разделитель [math]\displaystyle{ s_i }[/math], такой, что [math]\displaystyle{ k \in [s_{i - 1}, s_i) }[/math]. Если [math]\displaystyle{ k \in [s_0, s_1) }[/math], его положение определяется между O(1) базовыми разделителями под s1, и соответствующий базовый сегмент обновляется за время O(1) с использованием атомарной кучи над ключами этого сегмента. Если [math]\displaystyle{ k \in [s_{i - 1}, s_i) }[/math] для некоторого i > 1, обновление размещается во входном буфере [math]\displaystyle{ s_i }[/math], выполняя один шаг цикла [math]\displaystyle{ s_i }[/math] за время S(n) + O(1). Кроме того, во время каждого обновления выбирается еще один разделитель [math]\displaystyle{ s_r }[/math] в порядке круговой очереди, и фрагмент (1/log n) шага цикла [math]\displaystyle{ s_r }[/math] выполняется за время O(1). Работа с [math]\displaystyle{ s_r }[/math] гарантирует, что после каждых [math]\displaystyle{ O((log \; n)^2) }[/math] обновлений выполняется некоторое перемещение каждого верхнего разделителя.

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

Редукция в теореме 2

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

Последующие улучшения

В работе [1] Алструп и др. представили редукцию общего вида, преобразующую очередь с приоритетами с поддержкой операции вставки за время O(1) с сохранением всех остальных границ. Эту редукцию можно использовать для снижения стоимости вставки до константной в теоремах 1 и 2.

Применение

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

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

Открытые вопросы

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

См. также

• Сортировка без явного задания параметров кэша
• Внешние сортировка и перестановка
• Сортировка строк
• Построение суффиксного дерева в RAM-модели

Литература

1. Alstrup, S., Husfeldt, T., Rauhe, T., Thorup, M.: Black box for constant-time insertion in priority queues (note). ACM TALG 1(1),102-106(2005)

2. Andersson, A.: Faster deterministic sorting and searching in linear space. In: Proc. 37th FOCS, 1998, pp. 135-141

3. Andersson, A., Hagerup, T., Nilsson, S., Raman, R.: Sorting in linear time? J. Comp. Syst. Sci. 57, 74-93 (1998). Announced at STOC'95

4. Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge, MA (2001)

5. Fredman, M., Willard, D.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47, 424-436 (1993). Announced at STOC'90

6. Fredman, M., Willard, D.: Trans-dichotomous algorithms for minimum spanning trees and shortest paths. J. Comput. Syst. Sci. 48,533-551 (1994)

7. Fredman, M., Tarjan, R.: Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM 34(3), 596-615(1987)

8. Han, Y.: Improved fast integer sorting in linear space. Inf. Comput. 170(8), 81-94 (2001). Announced at STACS'00 and SODA'01

9. Han, Y.: Deterministic sorting in O(nloglogn) time and linear space. J. Algorithms 50(1), 96-105 (2004). Announced at STOC'02

10. Han, Y.,Thorup, M.: Integer sorting in O(nlog log n) expected time and linear space. In: Proc. 43rd FOCS, 2002, pp. 135-144

11. Mendelson, R., Tarjan, R., Thorup, M., Zwick, U.: Melding priority queues. ACM TALG 2(4), 535-556 (2006). Announced at SODA'04

12. Pagh, A., Pagh, R., Thorup, M.: On adaptive integer sorting. In: Proc. 12th ESA, 2004, pp. 556-579

13. Thorup, M.: Faster deterministic sorting and priority queues in linear space. In: Proc. 9th SODA, 1998, pp. 550-555

14. Thorup, M.: On RAM priority queues. SIAM J. Comput. 30(1), 86-109 (2000). Announced at SODA'96

15. Thorup, M.: Equivalence between priority queues and sorting. In: Proc. 43rd FOCS, 2002, pp. 125-134

16. Thorup, M.: Randomized sorting in O(nloglogn) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms 42(2), 205-230 (2002). Announced at SODA'97

17. Thorup, M.: Integer priority queues with decrease key in constant time and the single source shortest paths problem. J. Comput. Syst. Sci. (special issue on STOC'03) 69(3), 330-353 (2004)

18. Vollmer, H.: Introduction to circuit complexity: a uniform approach. Springer, New York (1999)

19. Willard, D.: Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree. SIAM J. Comput. 29(3), 1030-1049 (2000). Announced at SODA'92