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

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

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