Пирамидальная сортировка
Алгоритм сортировки, использующий структуру данных кучи

Пирамидальная сортировка
Выполнение пирамидальной сортировки, сортирующей массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются для удовлетворения свойства кучи . Перед фактической сортировкой для наглядности кратко показана структура дерева кучи.
СортАлгоритм сортировки
Структура данныхМножество
Худший вариант производительности О ( н бревно ⁡ н ) {\displaystyle O(n\log n)}
Лучшая производительность О ( н бревно ⁡ н ) {\displaystyle O(n\log n)} (различные ключи) [1] [2]
или (одинаковые ключи) О ( н ) {\displaystyle O(n)}
Средняя производительность О ( н бревно ⁡ н ) {\displaystyle O(n\log n)}
Наихудшая сложность пространства О ( н ) {\displaystyle O(n)} всего вспомогательный О ( 1 ) {\displaystyle O(1)}

В информатике пирамидальная сортировка — это эффективный алгоритм сортировки , основанный на сравнении , который реорганизует входной массив в кучу (структуру данных, в которой каждый узел больше своих дочерних узлов), а затем многократно удаляет самый большой узел из этой кучи, помещая его в конец массива. [3]

Хотя на практике на большинстве машин он несколько медленнее, чем хорошо реализованная быстрая сортировка , он имеет преимущества очень простой реализации и более благоприятного времени выполнения O ( n log n ) в худшем случае . Большинство реальных вариантов быстрой сортировки включают реализацию пирамидальной сортировки в качестве запасного варианта, если они обнаружат, что быстрая сортировка становится вырожденной. Пирамидальная сортировка — это алгоритм на месте , но это не стабильная сортировка .

Пирамидальная сортировка была изобретена Дж. У. Дж. Уильямсом в 1964 году. [4] В статье также была представлена ​​двоичная куча как полезная структура данных сама по себе. [5] В том же году Роберт У. Флойд опубликовал улучшенную версию, которая могла сортировать массив на месте, продолжив свои ранние исследования алгоритма сортировки деревьев . [5]

Обзор

Алгоритм пирамидальной сортировки можно разделить на две фазы: построение кучи и извлечение кучи.

Куча — это неявная структура данных , которая не занимает места за пределами массива объектов, подлежащих сортировке; массив интерпретируется как полное двоичное дерево , где каждый элемент массива является узлом, а родительские и дочерние связи каждого узла определяются простой арифметикой индексов массива. Для массива с нулевой базой корневой узел хранится под индексом 0, а узлы, связанные с узлом, iявляются

 iLeftChild(i) = 2⋅i + 1 iПравыйРебенок(i) = 2⋅i + 2 iParent(i) = пол((i−1) / 2)

где функция floor округляет вниз до предыдущего целого числа. Для более подробного объяснения см. Двоичная куча § Реализация кучи .

Это бинарное дерево является max-heap, когда каждый узел больше или равен обоим своим потомкам. Эквивалентно, каждый узел меньше или равен своему родителю. Это правило, применяемое ко всему дереву, приводит к тому, что максимальный узел располагается в корне дерева.

На первом этапе из данных строится куча (см. Двоичная куча § Построение кучи ).

На втором этапе куча преобразуется в сортированный массив путем многократного удаления наибольшего элемента из кучи (корня кучи) и помещения его в конец массива. Куча обновляется после каждого удаления для поддержания свойства кучи. После удаления всех объектов из кучи результатом становится сортированный массив.

Пирамидальная сортировка обычно выполняется на месте. На первом этапе массив делится на несортированный префикс и упорядоченный по куче суффикс (изначально пустой). Каждый шаг сжимает префикс и расширяет суффикс. Когда префикс пуст, эта фаза завершается. На втором этапе массив делится на упорядоченный по куче префикс и отсортированный суффикс (изначально пустой). Каждый шаг сжимает префикс и расширяет суффикс. Когда префикс пуст, массив сортируется.

Алгоритм

Алгоритм пирамидальной сортировки начинается с перестановки массива в двоичную максимальную кучу. Затем алгоритм многократно меняет местами корень кучи (наибольший элемент, оставшийся в куче) с ее последним элементом, который затем объявляется частью отсортированного суффикса. Затем куча, которая была повреждена заменой корня, восстанавливается так, что наибольший элемент снова оказывается в корне. Это повторяется до тех пор, пока в куче не останется только одно значение.

Шаги следующие:

  1. Вызовите heapify()функцию на массиве. Это создаст кучу из массива за O ( n ) операций.
  2. Поменять местами первый элемент массива (самый большой элемент в куче) с последним элементом кучи. Уменьшить рассматриваемый диапазон кучи на единицу.
  3. Вызовите siftDown()функцию для массива, чтобы переместить новый первый элемент на правильное место в куче.
  4. Возвращайтесь к шагу (2) до тех пор, пока оставшийся массив не станет одним элементом.

Операция heapify()выполняется один раз и имеет производительность O ( n )siftDown() . Функция вызывается n раз и требует O (log n ) работы каждый раз, поскольку ее обход начинается с корневого узла. Таким образом, производительность этого алгоритма составляет O ( n + n log n ) = O ( n log n ) .

Сердцем алгоритма является siftDown()функция. Она создает двоичные кучи из меньших куч и может рассматриваться двумя эквивалентными способами:

  • если даны две двоичные кучи и общий родительский узел, который не является частью ни одной из куч, объединить их в одну большую двоичную кучу; или
  • учитывая «поврежденную» двоичную кучу, где свойство max-heap (ни один дочерний элемент не больше своего родителя) выполняется везде, за исключением, возможно, узлов между корневым узлом и его дочерними элементами, восстановить ее, чтобы получить неповрежденную кучу.

Чтобы установить свойство max-heap в корне, необходимо сравнить до трех узлов (корень и два его потомка), и наибольший узел должен быть сделан корнем. Это проще всего сделать, найдя наибольшего потомка, а затем сравнив его с корнем. Есть три случая:

  1. Если дочерних элементов нет (две исходные кучи пусты), свойство кучи тривиально сохраняется, и никаких дальнейших действий не требуется.
  2. Если корень больше или равен наибольшему дочернему элементу, свойство кучи сохраняется и, аналогично, никаких дальнейших действий не требуется.
  3. Если корень меньше наибольшего потомка, поменяйте местами два узла. Свойство кучи теперь сохраняется в недавно повышенном узле (оно больше или равно обоим его потомкам, и фактически больше любого потомка), но может быть нарушено между недавно пониженным бывшим корнем и его новыми потомками. Чтобы исправить это, повторите операцию siftDown()на поддереве, корнем которого является недавно пониженный бывший корень.

Число итераций в одном siftdown()вызове ограничено высотой дерева, которая равна ⌊ log 2 n ⌋ = O (log n ) .

Псевдокод

Ниже приведен простой способ реализации алгоритма в псевдокоде . Массивы имеют нулевой базис и swapиспользуются для обмена двух элементов массива. Движение «вниз» означает от корня к листьям или от меньших индексов к большим. Обратите внимание, что во время сортировки наибольший элемент находится в корне кучи в a[0], тогда как в конце сортировки наибольший элемент находится в a[end].

процедура heapsort(a, count) имеет  входные данные: неупорядоченный массив a длины count  (Создайте кучу в массиве a так, чтобы наибольшее значение оказалось в корне) heapify(a, count) (Следующий цикл сохраняет инварианты , что a[0:end−1] является кучей, и  каждый элемент a[end:count−1] за пределами end больше, чем все элементы до него,  т.е. a[end:count−1] находится в отсортированном порядке.) конец ← количество while end > 1 do  (размер кучи уменьшается на единицу) конец ← конец − 1 (a[0] — корень и наибольшее значение. Перестановка перемещает его вперед отсортированных элементов.) поменять местами(a[конец], a[0]) (обмен испортил свойство кучи, поэтому восстановите его) siftDown(a, 0, конец)

Процедура сортировки использует две подпрограммы, heapifyи siftDown. Первая — это общая процедура построения кучи на месте, а вторая — общая подпрограмма для реализации heapify.

(Поместить элементы 'a' в порядке кучи, на месте) процедура heapify(a, count) - это  (start инициализируется первым конечным узлом)  (последний элемент в массиве, отсчитываемом от 0, имеет индекс count-1; найти родительский элемент этого элемента) начало ← iParent(count-1) + 1  while start > 0 do  (перейти к последнему узлу, не входящему в кучу) начать ← начать − 1 (просеиваем узел с индексом «start» до нужного места так, чтобы все узлы ниже  начального индекса располагались в порядке кучи) siftDown(a, начало, количество) (после просеивания вниз по корню все узлы/элементы располагаются в порядке кучи) (Восстановить кучу, корневой элемент которой находится по индексу 'start', предполагая, что кучи, корнем которых являются ее дочерние элементы, являются допустимыми) procedure siftDown(a, root, end) is  while iLeftChild(root) < end do  (Пока у корня есть хотя бы один дочерний элемент) child ← iLeftChild(root) (Левый дочерний элемент корня)  (Если есть правый дочерний элемент и этот дочерний элемент больше)  if child+1 < end and a[child] < a[child+1] then ребенок ← ребенок + 1  если а[корень] < а[ребенок] тогда swap(a[корень], a[ребенок]) root ← child (повторите, чтобы продолжить просеивание дочернего элемента)  else  (Корень содержит наибольший элемент. Поскольку мы можем предположить, что кучи, корнем которых являются дочерние элементы,  являются допустимыми, это означает, что мы закончили.)  return

Процедура heapifyработает путем построения небольших куч и многократного их слияния с помощью siftDown. Она начинается с листьев, замечая, что они являются тривиальными, но допустимыми кучами сами по себе, а затем добавляет родителей. Начиная с элемента n /2 и двигаясь в обратном направлении, каждый внутренний узел становится корнем допустимой кучи путем просеивания вниз. Последний шаг — просеивание вниз первого элемента, после чего весь массив подчиняется свойству кучи.

Чтобы увидеть, что это занимает O ( n ) времени, посчитайте наихудшее число siftDownитераций. Вторая половина массива требует ноль итераций, предыдущая четверть требует не более одной итерации, восьмая перед ней требует не более двух итераций, шестнадцатая перед ней требует не более трех и так далее.

Если посмотреть с другой стороны, если предположить, что каждый siftDownвызов требует максимального количества итераций, то первая половина массива потребует одну итерацию, первая четверть — еще одну (всего 2), первая восьмая — еще одну (всего 3) и т. д.

Это дает в сумме n /2 + n /4 + n /8 + ⋯ = n⋅(1/2 + 1/4 + 1/8 + ⋯) , где бесконечная сумма — это хорошо известная геометрическая прогрессия , сумма которой равна 1 , поэтому произведение просто равно n .

Вышеприведенное является приближением. Точное наихудшее число сравнений во время фазы построения кучи пирамидальной сортировки, как известно, равно 2 n − 2 s 2 ( n ) − e 2 ( n ) , где s 2 ( n ) — это количество битов 1 в двоичном представлении n , а e 2 ( n ) — это количество конечных битов 0 . [6] [7]

Стандартная реализация

Хотя удобно думать о двух фазах по отдельности, большинство реализаций объединяют их, позволяя одному экземпляру siftDownбыть развернутым в строке . [8] : Алгоритм H  Две переменные (здесь, startи end) отслеживают границы области кучи. Часть массива до startне отсортирована, в то время как часть, начинающаяся с , endотсортирована. Построение кучи уменьшается , startпока не станет равным нулю, после чего извлечение кучи уменьшается, endпока не станет равным 1, и массив будет полностью отсортирован.

процедура heapsort(a, count) имеет  входные данные: неупорядоченный массив a длины count  начало ← этаж(кол-во/2) конец ← количество while end > 1 do  if start > 0 then  (конструкция кучи) начать ← начать − 1 иначе  (извлечение кучи) конец ← конец − 1 поменять местами(a[конец], a[0])  (Далее — siftDown(a, start, end)) корень ← начало пока iLeftChild(root) < конец делать child ← iLeftChild(корень) (Если есть правый потомок и этот потомок больше)  если потомок+1 < конец и a[ребенок] < a[ребенок+1] тогда ребенок ← ребенок + 1  если а[корень] < а[ребенок] тогда swap(a[корень], a[ребенок]) root ← child (повторить, чтобы продолжить просеивание потомка)  в противном случае  break  (вернуться к внешнему циклу)

Вариации

Конструкция кучи Уильямса

Описание выше использует улучшенный алгоритм построения кучи Флойда, который работает за время O ( n ) и использует тот же siftDownпримитив, что и фаза извлечения кучи. Хотя этот алгоритм, будучи и более быстрым, и более простым в программировании, используется всеми практическими реализациями пирамидальной сортировки, оригинальный алгоритм Уильямса может быть более понятным и необходим для реализации более общей двоичной очереди приоритетов кучи .

Вместо того, чтобы объединять множество маленьких куч, алгоритм Уильямса поддерживает одну единственную кучу в начале массива и многократно добавляет дополнительный элемент с помощью siftUpпримитива. Находясь в конце массива, новый элемент является листом и не имеет потомков, о которых нужно беспокоиться, но может нарушить свойство кучи, будучи больше своего родителя. В этом случае поменяйте его с его родителем и повторяйте тест, пока родитель не станет больше или не останется ни одного родителя (мы достигли корня). В псевдокоде это выглядит так:

 процедура siftUp(a, end) имеет  входные данные:  a — массив, упорядоченный по куче до end-1.  end — узел для просеивания.  while end > 0 родитель := iParent(конец) если a[parent] < a[end] тогда  (вне максимального порядка кучи) swap(a[родитель], a[конец]) конец := родитель (продолжить просеивание)  иначе  возврат  процедура heapify(a, count) — это  (начнем с тривиальной одноэлементной кучи) конец := 1  while end < count (просеиваем узел с индексом end до нужного места так, чтобы  все узлы выше конечного индекса располагались в порядке кучи) просеятьВверх(а, конец) конец := конец + 1 (после просеивания последнего узла все узлы располагаются в порядке кучи)
Разница во временной сложности между версиями «siftDown» и «siftUp».

Чтобы понять, почему этот алгоритм может занять асимптотически больше времени для построения кучи ( O ( n log n ) против O ( n ) в худшем случае), обратите внимание, что в алгоритме Флойда почти все вызовы siftDownопераций применяются к очень маленьким кучам. Половина куч являются тривиальными кучами высоты 1 и могут быть полностью пропущены, половина оставшихся — высотой 2 и т. д. Только два вызова выполняются для куч размером n /2 , и только одна siftDownоперация выполняется для полной кучи из n элементов. Общая средняя siftDownоперация занимает O (1) времени.

Напротив, в алгоритме Уильямса большинство вызовов siftUpпроизводятся на больших кучах высотой O (log n ) . Половина вызовов производится с размером кучи n /2 или более, три четверти производятся с размером кучи n /4 или более и т. д. Хотя среднее число шагов похоже на технику Флойда, [9] : 3  предварительно отсортированных входных данных приведут к наихудшему случаю: каждый добавленный узел просеивается до корня, поэтому средний вызов siftUpпотребует приблизительно (log 2 n − 1)/2 + (log 2 n − 2)/4 + (log 2 n − 3)/8 + ⋯ = log 2 n − (1 + 1/2 + 1/4 + ⋯) = log 2 n − 2 итераций.

Поскольку в нем доминирует вторая фаза извлечения кучи, сам алгоритм пирамидальной сортировки имеет временную сложность O ( n log n ) при использовании любой версии heapify.

Пирамидальная сортировка снизу вверх

Пирамидальная сортировка снизу вверх — это вариант, который уменьшает количество требуемых сравнений на значительный фактор. В то время как обычная пирамидальная сортировка сверху вниз требует 2 n log 2 n + O ( n ) сравнений в худшем случае и в среднем [10] , вариант снизу вверх требует n log 2 n + O (1) сравнений в среднем [10] и 1,5 n log 2 n + O ( n ) в худшем случае. [11]

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

Это достигается с помощью более сложной siftDownпроцедуры. Изменение немного улучшает фазу линейного времени построения кучи, [13] , но более существенно во второй фазе. Как и в нисходящей пирамидальной сортировке, каждая итерация второй фазы извлекает вершину кучи, a[0]и заполняет образовавшийся пробел с помощью a[end], затем просеивает этот последний элемент вниз по куче. Но этот элемент пришел с самого нижнего уровня кучи, то есть это один из самых маленьких элементов в куче, поэтому просеивание вниз, вероятно, потребует много шагов, чтобы переместить его обратно вниз. [14] В нисходящей пирамидальной сортировке каждый шаг siftDownтребует двух сравнений, чтобы найти минимум из трех элементов: новый узел и его двух дочерних элементов.

Пирамидальная сортировка снизу вверх концептуально заменяет корень значением −∞ и просеивает его вниз, используя только одно сравнение на уровень (поскольку ни один дочерний элемент не может быть меньше −∞), пока не будут достигнуты листья, затем заменяет −∞ правильным значением и просеивает его вверх (опять же, используя одно сравнение на уровень), пока не будет найдена правильная позиция.

Это помещает корень в то же место, что и сверху вниз siftDown, но для нахождения этого места требуется меньше сравнений. Для любой отдельной siftDownоперации техника снизу вверх выгодна, если количество движений вниз составляет не менее 2 ⁄ 3 высоты дерева (когда количество сравнений составляет 4 ⁄ 3 высоты для обеих техник), и оказывается, что это более чем верно в среднем, даже для наихудших входных данных. [11]

Наивная реализация этого концептуального алгоритма привела бы к избыточному копированию данных, поскольку просеивание вверх отменяет часть просеивания вниз. Практическая реализация ищет вниз лист, где будет размещено −∞, затем вверх, где должен быть размещен корень . Наконец, восходящий обход продолжается до начальной позиции корня, не выполняя больше сравнений, но обмениваясь узлами для завершения необходимой перестановки. Эта оптимизированная форма выполняет то же количество обменов, что и сверху вниз siftDown.

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

Функция leafSearch(a, i, end) — это ж ← я while iRightChild(j) < end do  (Определить, какой из двух дочерних элементов j больше)  if a[iRightChild(j)] > a[iLeftChild(j)] then j ← iПравыйРебенок(j) еще j ← iLeftChild(j) (На последнем уровне может быть только один дочерний элемент)  если iLeftChild(j) < end тогда j ← iLeftChild(j) возвращение j

Возвращаемое значение leafSearchиспользуется в измененной siftDownпроцедуре: [11]

процедура siftDown(a, i, end) — это j ← листПоиск(a, i, конец) пока a[i] > a[j] делают j ← iРодитель(j) пока j > я делаю поменять местами(a[i], a[j]) j ← iРодитель(j)

Было объявлено, что пирамидальная сортировка снизу вверх превосходит быструю сортировку (с медианным выбором из трех опорных элементов) на массивах размером ≥16000. [10]

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

Дальнейшее уточнение выполняет бинарный поиск в восходящем поиске и сортирует в худшем случае ( n +1)(log 2 ( n +1) + log 2 log 2 ( n +1) + 1,82) + O (log 2 n ) сравнений, приближаясь к информационной теоретико-нижней границе n log 2 n − 1,4427 n сравнений. [16]

Вариант, который использует два дополнительных бита на внутренний узел ( всего n −1 бит для n -элементной кучи) для кэширования информации о том, какой дочерний элемент больше (для хранения трех случаев: левый, правый и неизвестный требуется два бита) [13], использует менее n log 2 n + 1,1 n сравнений. [17]

Другие вариации

  • Тернарная пирамидальная сортировка использует тернарную кучу вместо двоичной кучи; то есть каждый элемент в куче имеет три дочерних элемента. Она сложнее в программировании, но выполняет в постоянное число раз меньше операций обмена и сравнения. Это связано с тем, что каждый шаг просеивания вниз в троичной куче требует трех сравнений и одного обмена, тогда как в двоичной куче требуются два сравнения и один обмен. Два уровня в троичной куче покрывают 3 2 = 9 элементов, выполняя больше работы с тем же количеством сравнений, что и три уровня в двоичной куче, которые покрывают только 2 3 = 8. [ требуется ссылка ] Это в первую очередь представляет академический интерес или как студенческое упражнение, [18], поскольку дополнительная сложность не стоит незначительной экономии, а пирамидальная сортировка снизу вверх превосходит оба.
  • Оптимизированная для памяти пирамидальная сортировка [19] : 87  улучшает локальность ссылок пирамидальной сортировки , еще больше увеличивая количество потомков. Это увеличивает количество сравнений, но поскольку все потомки хранятся в памяти последовательно, сокращает количество строк кэша, к которым осуществляется доступ во время обхода кучи, что является чистым улучшением производительности.
  • Стандартная реализация алгоритма построения кучи Флойда приводит к большому количеству промахов кэша , как только размер данных превышает размер кэша процессора . [19] : 87  Более высокую производительность на больших наборах данных можно получить путем слияния в порядке глубины , объединяя подкучи как можно скорее, а не объединяя все подкучи на одном уровне перед переходом на уровень выше. [9] [20]
  • Пирамидальная сортировка вне места [21] [22] [14] улучшает пирамидальную сортировку снизу вверх, исключая наихудший случай, гарантируя n log 2 n + O ( n ) сравнений. Когда берется максимум, вместо того, чтобы заполнять освободившееся пространство несортированным значением данных, заполняйте его −∞ контрольным значением, которое никогда не «отскакивает» обратно. Оказывается, это можно использовать в качестве примитива в алгоритме «QuickHeapsort» на месте (и нерекурсивном). [23] Сначала вы выполняете проход разбиения, подобный быстрой сортировке, но меняя порядок разбиения данных в массиве на обратный. Предположим ( без потери общности ), что меньший раздел — это тот, который больше опорного элемента, который должен находиться в конце массива, но наш шаг обратного разбиения помещает его в начало. Сформируйте кучу из меньшего раздела и выполните на нем пирамидальную сортировку вне места, заменив извлеченные максимумы на значения из конца массива. Они меньше опорного элемента, то есть меньше любого значения в куче, поэтому служат в качестве −∞ контрольных значений. После завершения пирамидальной сортировки (и опорного элемента, перемещенного непосредственно перед отсортированным концом массива) порядок разделов меняется на обратный, и больший раздел в начале массива может быть отсортирован таким же образом. (Поскольку нет нехвостовой рекурсии , это также исключает использование стека O (log n ) быстрой сортировки .)
  • Алгоритм плавной сортировки [24] является вариацией пирамидальной сортировки, разработанной Эдсгером В. Дейкстрой в 1981 году . Как и пирамидальная сортировка, верхняя граница плавной сортировки составляет O ( n log n ) . Преимущество плавной сортировки в том, что она приближается к O ( n ) времени, если входные данные уже отсортированы до некоторой степени , тогда как пирамидальная сортировка в среднем составляет O ( n log n ) независимо от начального отсортированного состояния. Из-за своей сложности плавная сортировка используется редко. [ необходима цитата ]
  • Левкопулос и Петерссон [25] описывают вариацию пирамидальной сортировки, основанную на куче декартовых деревьев . Сначала декартово дерево строится из входных данных за время O ( n ) , а его корень помещается в двоичную кучу из 1 элемента. Затем мы многократно извлекаем минимум из двоичной кучи, выводим корневой элемент дерева и добавляем его левых и правых потомков (если таковые имеются), которые сами являются декартовыми деревьями, в двоичную кучу. [26] Как они показывают, если входные данные уже почти отсортированы, декартовы деревья будут очень несбалансированными, с немногими узлами, имеющими левых и правых потомков, в результате чего двоичная куча остается небольшой и позволяет алгоритму сортировать быстрее, чем O ( n log n ) для входных данных, которые уже почти отсортированы.
  • Несколько вариантов, таких как слабая пирамидальная сортировка, требуют n log 2 n + O (n) сравнений в худшем случае, близко к теоретическому минимуму, используя один дополнительный бит состояния на узел. Хотя этот дополнительный бит делает алгоритмы не совсем на месте, если для него можно найти место внутри элемента, эти алгоритмы просты и эффективны, [9] : 40  , но все еще медленнее, чем двоичные пирамиды, если сравнения ключей достаточно дешевы (например, целочисленные ключи), так что постоянный множитель не имеет значения. [27]
  • «Окончательная пирамидальная сортировка» Катаяйнена не требует дополнительного хранилища, выполняет n log 2 n + O (n) сравнений и аналогичное количество перемещений элементов. [28] Однако она еще более сложна и не оправдана, если только сравнения не являются очень затратными.

Сравнение с другими сортами

Пирамидальная сортировка в первую очередь конкурирует с быстрой сортировкой — другим очень эффективным универсальным алгоритмом сортировки, основанным на нестабильном сравнении на месте.

Главными преимуществами пирамидальной сортировки являются ее простой, нерекурсивный код , минимальные требования к вспомогательной памяти и надежно хорошая производительность: ее лучшие и худшие случаи находятся в пределах небольшого постоянного множителя друг от друга и теоретической нижней границы сравнительных сортировок . Хотя она не может превзойти O ( n log n ) для предварительно отсортированных входных данных, она также не страдает от худшего случая быстрой сортировки O ( n 2 ) .

Реализации быстрой сортировки в реальном мире используют различные эвристики , чтобы избежать худшего случая, но это делает их реализацию намного более сложной, и такие реализации, как introsort и pattern-defeating quicksort [29], используют пирамидальную сортировку в качестве последнего средства отката, если они обнаруживают вырожденное поведение. Таким образом, их производительность в худшем случае немного хуже, чем если бы пирамидальная сортировка использовалась с самого начала.

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

Гарантии производительности в худшем случае делают пирамидальную сортировку популярной в вычислениях в реальном времени и системах, связанных с вредоносным выбором входных данных [30], таких как ядро ​​Linux. [31] Сочетание небольшой реализации и надежной «достаточно хорошей» производительности делает ее популярной во встраиваемых системах и, в целом, в любых приложениях, где сортировка не является узким местом производительности . Например, пирамидальная сортировка идеально подходит для сортировки списка имен файлов для отображения, но система управления базами данных , вероятно, захочет более агрессивно оптимизированный алгоритм сортировки.

Хорошо реализованная быстрая сортировка обычно в 2–3 раза быстрее пирамидальной сортировки. [19] [32] Хотя быстрая сортировка требует меньше сравнений, это незначительный фактор. (Результаты, утверждающие, что в два раза больше сравнений, измеряют версию сверху вниз; см. § Пирамидальная сортировка снизу вверх.) Главное преимущество быстрой сортировки — гораздо лучшая локальность ссылок: разбиение представляет собой линейное сканирование с хорошей пространственной локальностью, а рекурсивное подразделение имеет хорошую временную локальность. При дополнительных усилиях быструю сортировку можно реализовать в коде, в основном без ветвлений , [33] [34] , и для параллельной сортировки подразделов можно использовать несколько ЦП. Таким образом, быстрая сортировка предпочтительнее, когда дополнительная производительность оправдывает усилия по реализации.

Другой основной алгоритм сортировки O ( n log n ) — сортировка слиянием , но он редко конкурирует напрямую с пирамидальной сортировкой, поскольку она не является локальной. Требование сортировки слиянием для Ω( n ) дополнительного пространства (примерно половина размера входных данных) обычно является запретительным, за исключением ситуаций, когда сортировка слиянием имеет явное преимущество:

  • Когда требуется стабильная сортировка
  • При использовании (частично) предварительно отсортированных входных данных
  • Сортировка связанных списков (в этом случае сортировка слиянием требует минимального дополнительного пространства)
  • Параллельная сортировка; сортировка слиянием распараллеливается даже лучше, чем быстрая сортировка, и может легко достигать почти линейного ускорения.
  • Внешняя сортировка ; сортировка слиянием имеет превосходную локальность ссылок.

Пример

Примеры сортируют значения { 6, 5, 3, 1, 8, 7, 2, 4 } в порядке возрастания с использованием обоих алгоритмов построения кучи. Сравниваемые элементы показаны жирным шрифтом. Обычно их два при просеивании вверх и три при просеивании вниз, хотя их может быть меньше, когда достигается вершина или низ дерева.

Построение кучи (алгоритм Вильямса)

Пример пирамидальной сортировки с использованием алгоритма построения кучи Уильямса.
КучаНесортированныйПоменять местами элементы
65, 3, 1, 8, 7, 2, 4
6 , 53, 1, 8, 7, 2, 4
6 , 5, 31, 8, 7, 2, 4
6, 5 , 3, 18, 7, 2, 4
6, 5 , 3, 1, 87, 2, 45 ↔ 8
6 , 8 , 3, 1, 57, 2, 46 ↔ 8
8 , 6, 3, 1, 57, 2, 4
8, 6, 3 , 1, 5, 72, 43 ↔ 7
8 , 6, 7 , 1, 5, 32, 4
8, 6, 7 , 1, 5, 3, 24
8, 6, 7, 1 , 5, 3, 2, 41 ↔ 4
8, 6 , 7, 4 , 5, 3, 2, 1

Построение кучи (алгоритм Флойда)

НесортированныйКучаПоменять местами элементы
6, 5, 3, 18, 7, 2, 4
6, 5, 31 , 8, 7, 2, 41 ↔ 4
6, 5, 34, 8, 7, 2, 1
6, 53 , 4, 8, 7 , 2 , 13 ↔ 7
6, 57, 4, 8, 3 , 2, 1
65 , 7, 4 , 8 , 3, 2, 15 ↔ 8
68, 7, 4, 5 , 3, 2, 1
6 , 8 , 7 , 4, 5, 3, 2, 16 ↔ 8
8, 6 , 7, 4 , 5 , 3, 2, 1

Извлечение кучи

КучаСортированный массивПоменять местами элементыПодробности
8 , 6, 7, 4, 5, 3, 2, 18 ↔ 1Добавьте 8 к отсортированному массиву, поменяв его местами с 1.
1 , 6 , 7 , 4, 5, 3, 281 ↔ 7Поменяйте местами 1 и 7, так как они не в том порядке в куче.
7, 6, 1 , 4, 5, 3 , 281 ↔ 3Поменяйте местами 1 и 3, так как они не в том порядке в куче.
7, 6, 3, 4, 5, 1 , 281 не имеет потомков; siftDown завершен
7 , 6, 3, 4, 5, 1, 287 ↔ 2Добавьте 7 к отсортированному массиву, поменяв его местами с 2
2 , 6 , 3 , 4, 5, 17, 82 ↔ 6Поменяйте местами 2 и 6, так как они не в том порядке в куче.
6, 2 , 3, 4 , 5 , 17, 82 ↔ 5Поменяйте местами 2 и 5, так как они не в том порядке в куче.
6, 5, 3, 4, 2 , 17, 82 не имеет потомков; siftDown завершен
6 , 5, 3, 4, 2, 17, 86 ↔ 1Добавьте 6 к отсортированному массиву, поменяв его местами с 1.
1 , 5 , 3 , 4, 26, 7, 81 ↔ 5Поменяйте местами 1 и 5, так как они не в том порядке в куче.
5, 1 , 3, 4 , 26, 7, 81 ↔ 4Поменяйте местами 1 и 4, так как они не в том порядке в куче.
5, 4, 3, 1 , 26, 7, 81 не имеет потомков; siftDown завершен
5 , 4, 3, 1, 26, 7, 85 ↔ 2Добавьте 5 к отсортированному массиву, поменяв его местами с 2
2 , 4 , 3 , 15, 6, 7, 82 ↔ 4Поменяйте местами 2 и 4, так как они не в том порядке в куче.
4, 2 , 3, 15, 6, 7, 82 больше 1; siftDown завершен
4 , 2, 3, 15, 6, 7, 84 ↔ 1Добавьте 4 к отсортированному массиву, поменяв его местами с 1
1 , 2 , 34, 5, 6, 7, 81 ↔ 3Поменяйте местами 1 и 3, так как они не в том порядке в куче.
3, 2, 14, 5, 6, 7, 81 не имеет потомков; siftDown завершен
3 , 2, 14, 5, 6, 7, 81 ↔ 3Добавьте 3 к отсортированному массиву, поменяв его местами с 1.
1 , 23, 4, 5, 6, 7, 81 ↔ 2Поменяйте местами 1 и 2, так как они не в том порядке в куче.
2, 13, 4, 5, 6, 7, 81 не имеет потомков; siftDown завершен
2 , 13, 4, 5, 6, 7, 82 ↔ 1Добавьте 2 к отсортированному массиву, поменяв его местами с 1.
12, 3, 4, 5, 6, 7, 8Добавить 1 к отсортированному массиву
1, 2, 3, 4, 5, 6, 7, 8Завершенный

Примечания

  1. ^ Боллобас, Б.; Феннер, ТИ; Фриз, АМ (1996). «О лучшем случае пирамидальной сортировки» (PDF) . Журнал алгоритмов . 20 (11): 205–217 . doi :10.1006/jagm.1996.0011.
  2. ^ Седжвик, Роберт ; Шаффер, Рассел В. (октябрь 1990 г.). Лучший случай пирамидальной сортировки (технический отчет). Принстонский университет. TR-293-90.
  3. ^ Кормен, Томас Х.; Лейзерсон, Чарльз Эрик; Ривест, Рональд Л.; Стайн, Клиффорд (2022). Введение в алгоритмы (4-е изд.). Кембридж, Массачусетс: The MIT Press. стр. 170. ISBN 978-0-262-04630-5.
  4. ^ Уильямс 1964
  5. ^ ab Brass, Peter (2008). Advanced Data Structures . Cambridge University Press. стр. 209. ISBN 978-0-521-88037-4.
  6. ^ Suchenek, Marek A. (2012). «Элементарный, но точный анализ худшего случая программы построения кучи Флойда». Fundamenta Informaticae . 120 (1): 75–92 . doi :10.3233/FI-2012-751.
  7. ^ Сученек, Марек А. (7 апреля 2015 г.). «Полный анализ пирамидальной сортировки в худшем случае с экспериментальной проверкой его результатов, рукопись». arXiv : 1504.01459 [cs.DS].
  8. ^ Кнут 1997
  9. ^ abc Bojesen, Jesper; Katajainen, Jyrki; Spork, Maz (2000). "Performance Engineering Case Study: Heap Construction" (PostScript) . ACM Journal of Experimental Algorithmics . 5 (15): 15–es. CiteSeerX 10.1.1.35.3248 . doi :10.1145/351827.384257. S2CID  30995934. Альтернативный источник PDF.
  10. ^ abc Wegener, Ingo (13 сентября 1993 г.). "BOTTOM-UP HEAPSORT, новый вариант HEAPSORT, превосходящий в среднем QUICKSORT (если n не очень мало)" (PDF) . Теоретическая информатика . 118 (1): 81– 98. doi : 10.1016/0304-3975(93)90364-y .Хотя это перепечатка работы, впервые опубликованной в 1990 году (на конференции «Математические основы информатики»), сама методика была опубликована Карлссоном в 1987 году. [16]
  11. ^ abc Флейшер, Рудольф (февраль 1994 г.). "Жесткая нижняя граница для худшего случая пирамидальной сортировки снизу вверх" (PDF) . Algorithmica . 11 (2): 104– 115. doi :10.1007/bf01182770. hdl : 11858/00-001M-0000-0014-7B02-C . S2CID  21075180.Также доступно как Fleischer, Rudolf (апрель 1991 г.). Точная нижняя граница для худшего случая Bottom-Up-Heapsort (PDF) (Технический отчет). MPI-INF . MPI-I-91-104.
  12. ^ ab Mehlhorn, Kurt ; Sanders, Peter (2008). "Очереди с приоритетом" (PDF) . Алгоритмы и структуры данных: базовый набор инструментов. Springer. стр. 142. ISBN 978-3-540-77977-3.
  13. ^ ab McDiarmid, CJH; Reed, BA (сентябрь 1989). "Строим кучи быстро" (PDF) . Журнал алгоритмов . 10 (3): 352– 365. doi :10.1016/0196-6774(89)90033-3.
  14. ^ ab MacKay, David JC (декабрь 2005 г.). "Пирамидная сортировка, быстрая сортировка и энтропия" . Получено 12 февраля 2021 г.
  15. ^ Морет, Бернард ; Шапиро, Генри Д. (1991). "8.6 Пирамидальная сортировка". Алгоритмы от P до NP. Том 1: Разработка и эффективность . Benjamin/Cummings. стр. 528. ISBN 0-8053-8008-6. За неимением лучшего названия мы называем эту улучшенную программу «пирамидальная сортировка с отскоком » .
  16. ^ ab Carlsson, Scante (март 1987). "Вариант пирамидальной сортировки с почти оптимальным числом сравнений" (PDF) . Information Processing Letters . 24 (4): 247– 250. doi :10.1016/0020-0190(87)90142-6. S2CID  28135103. Архивировано из оригинала (PDF) 27 декабря 2016 г.
  17. ^ Вегенер, Инго (март 1992). "Сложность в худшем случае варианта Макдиармида и Рида BOTTOM-UP HEAPSORT меньше, чем n log n + 1.1n". Информация и вычисления . 97 (1): 86– 96. doi : 10.1016/0890-5401(92)90005-Z .
  18. ^ Тененбаум, Аарон М.; Огенштейн, Моше Дж. (1981). "Глава 8: Сортировка". Структуры данных с использованием Паскаля . Prentice-Hall. стр. 405. ISBN 0-13-196501-8. Напишите процедуру сортировки, похожую на пирамидальную сортировку, за исключением того, что она использует троичную кучу.
  19. ^ abc LaMarca, Anthony; Ladner, Richard E. (апрель 1999 г.). «Влияние кэшей на производительность сортировки» (PDF) . Journal of Algorithms . 31 (1): 66– 104. CiteSeerX 10.1.1.456.3616 . doi :10.1006/jagm.1998.0985. S2CID  206567217. См. в частности рисунок 9c на стр. 98.
  20. ^ Чен, Джингсен; Эделькамп, Стефан; Элмасри, Амр; Катаяйнен, Юрки (27–31 августа 2012 г.). «Построение кучи на месте с оптимизированными сравнениями, перемещениями и промахами кэша» (PDF) . Математические основы информатики 2012 г. . 37-я международная конференция по математическим основам информатики. Конспект лекций по информатике. Том 7464. Братислава, Словакия. стр.  259–270 . doi :10.1007/978-3-642-32589-2_25. ISBN 978-3-642-32588-5. S2CID  1462216. Архивировано из оригинала (PDF) 29 декабря 2016 г.См. в частности рис. 3.
  21. ^ Кантоне, Доменико; Конкотти, Джанлука (1–3 марта 2000 г.). QuickHeapsort, эффективное сочетание классических алгоритмов сортировки. 4-я итальянская конференция по алгоритмам и сложности. Конспект лекций по информатике. Том 1767. Рим. С.  150–162 . ISBN 3-540-67159-5.
  22. ^ Кантоне, Доменико; Конкотти, Джанлука (август 2002 г.). «QuickHeapsort, эффективное сочетание классических алгоритмов сортировки» (PDF) . Теоретическая информатика . 285 (1): 25– 42. doi : 10.1016/S0304-3975(01)00288-2 . Zbl  1016.68042.
  23. ^ Diekert, Volker; Weiß, Armin (август 2016 г.). «QuickHeapsort: Modifications and improved analysis». Теория вычислительных систем . 59 (2): 209– 230. arXiv : 1209.4214 . doi : 10.1007/s00224-015-9656-y. S2CID  792585.
  24. ^ Дейкстра, Эдсгер В. Гладкая сортировка – альтернатива сортировке на месте (EWD-796a) (PDF) . Архив Э. В. Дейкстры. Центр американской истории, Техасский университет в Остине .(транскрипция)
  25. ^ Левкопулос, Христос; Петерссон, Ола (1989). «Пирамидная сортировка — адаптированная для предварительно отсортированных файлов». WADS '89: Труды семинара по алгоритмам и структурам данных . Конспект лекций по информатике. Том 382. Лондон, Великобритания: Springer-Verlag. С.  499– 509. doi :10.1007/3-540-51542-9_41. ISBN 978-3-540-51542-5.Пирамидальная сортировка — адаптирована для предварительно отсортированных файлов (Q56049336).
  26. ^ Шварц, Кит (27 декабря 2010 г.). "CartesianTreeSort.hh". Архив интересного кода . Получено 5 марта 2019 г. .
  27. ^ Катаяйнен, Юрки (23 сентября 2013 г.). Поиск наилучшей очереди приоритетов: извлеченные уроки. Алгоритмическая инженерия (семинар 13391). Dagstuhl. стр.  19–20 , 24.
  28. ^ Катаяйнен, Юрки (2–3 февраля 1998 г.). The Ultimate Heapsort. Вычисления: 4-й Австралазийский теоретический симпозиум. Australian Computer Science Communications . Т. 20, № 3. Перт. С.  87–96 .
  29. ^ Питерс, Орсон РЛ (9 июня 2021 г.). «Быстрая сортировка, побеждающая шаблоны». arXiv : 2106.05123 [cs.DS].
    Peters, Orson RL "pdqsort". Github . Получено 2 октября 2023 г. .
  30. ^ Моррис, Джон (1998). «Сравнение быстрой и пирамидальной сортировки». Структуры данных и алгоритмы (конспекты лекций). Университет Западной Австралии . Получено 12 февраля 2021 г.
  31. ^ https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/sort.c#n205 Исходный код ядра Linux
  32. ^ Maus, Arne [на норвежском языке] (14 мая 2014 г.). «Сортировка путем генерации сортировочной перестановки и влияние кэширования на сортировку».См. рис. 1 на стр. 6.
  33. ^ Эделькамп, Стефан; Вайс, Армин (30 января 2019 г.). «BlockQuicksort: предотвращение неверных прогнозов ветвей при быстрой сортировке» (PDF) . Журнал экспериментальной алгоритмики . 24 1.4. arXiv : 1604.06697 . дои : 10.1145/3274660.
  34. ^ Аумюллер, Мартин; Хасс, Николай (7–8 января 2019 г.). Простая и быстрая блочная сортировка с использованием схемы разбиения Ломуто. Двадцать первый семинар по разработке алгоритмов и экспериментам (ALENEX). Сан-Диего. arXiv : 1810.12047 . doi : 10.1137/1.9781611975499.2 .

Ссылки

Реализация алгоритма Wikibook имеет страницу по теме: Пирамидальная сортировка
  • Анимированные алгоритмы сортировки: пирамидальная сортировка на Wayback Machine (архив 6 марта 2015 г.) – графическая демонстрация
  • Учебное пособие по пирамидальной сортировке от Университета Ольденбурга – с текстом, анимацией и интерактивными упражнениями
  • Словарь алгоритмов и структур данных NIST: Пирамидальная сортировка
  • Пирамидальная сортировка реализована на 12 языках Архивировано 28 декабря 2010 г. на Wayback Machine
  • Повторный взгляд на сортировку от Пола Шея
  • Презентация PowerPoint, демонстрирующая принцип работы пирамидальной сортировки, предназначенная для преподавателей.
  • Открытые структуры данных – Раздел 11.1.3 – Пирамидальная сортировка, Пэт Морин
Получено с "https://en.wikipedia.org/w/index.php?title=Heapsort&oldid=1270462231"