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

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

Куча

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

Очередь с приоритетами представляет собой абстрактную структуру данных, поддерживающую множество из 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). Далее изложим эту технологию более подробно.

Отсортированный список ключей: