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

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

Куча

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

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