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

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

Куча

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

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

meld(Q1, Q2): получая на вход очереди с приоритетами Q1 и Q2, выдает очередь с приоритетом Q1 [ Q2.

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

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