Heapsort - Heapsort

Heapsort
Сортировка heapsort anim.gif
Запуск heapsort, сортирующий массив случайно переставленных значений. На первом этапе алгоритма элементы массива переупорядочиваются, чтобы удовлетворить куча собственности. Перед фактической сортировкой для иллюстрации кратко показана древовидная структура кучи.
Учебный классАлгоритм сортировки
Структура данныхМножество
Худший случай спектакль
Лучший случай спектакль (отдельные ключи)
или же (одинаковые ключи)
Средний спектакль
Худший случай космическая сложность общий вспомогательный

В Информатика, heapsort это на основе сравнения алгоритм сортировки. Heapsort можно рассматривать как улучшенный сортировка выбора: подобно сортировке по выбору, heapsort делит входные данные на отсортированную и несортированную область и итеративно сжимает несортированную область, извлекая из нее самый большой элемент и вставляя его в отсортированную область. В отличие от сортировки по выбору, heapsort не тратит время на линейное сканирование несортированной области; скорее, сортировка кучи поддерживает несортированную область в куча структура данных, чтобы быстрее находить самый большой элемент на каждом этапе.[1]

Хотя на практике на большинстве машин несколько медленнее, чем хорошо реализованный быстрая сортировка, он имеет преимущество в более благоприятном наихудшем случае O (п бревно п) время выполнения. Heapsort - это алгоритм на месте, но это не стабильная сортировка.

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

Обзор

Алгоритм heapsort можно разделить на две части.

На первом этапе куча построен на основе данных (см. Двоичная куча § Создание кучи ). Куча часто помещается в массив с разметкой полного двоичное дерево. Полное двоичное дерево отображает структуру двоичного дерева в индексы массива; каждый индекс массива представляет узел; индекс родительского узла, левой дочерней ветви или правой дочерней ветви - это простые выражения. Для массива, начинающегося с нуля, корневой узел хранится с индексом 0; если я это индекс текущего узла, тогда

  iParent (i) = floor ((i-1) / 2), где функции этажа сопоставляют действительное число с наименьшим ведущим целым числом. iLeftChild (i) = 2 * i + 1 iRightChild (i) = 2 * i + 2

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

Heapsort может выполняться на месте. Массив можно разделить на две части: отсортированный массив и кучу. Схема хранения куч в виде массивов Вот. Инвариант кучи сохраняется после каждого извлечения, поэтому единственная стоимость - извлечение.

Алгоритм

Алгоритм Heapsort включает подготовку списка, сначала превращая его в максимальная куча. Затем алгоритм несколько раз меняет местами первое значение списка на последнее значение, уменьшая диапазон значений, учитываемых в операции кучи, на единицу и просеивая новое первое значение в его позицию в куче. Это повторяется до тех пор, пока диапазон рассматриваемых значений не станет длиной в одно значение.

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

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

Операция buildMaxHeap () запускается один раз и O (п) в исполнении. Функция siftDown () - это O (журналп), и называется п раз. Следовательно, производительность этого алгоритма O (п + п бревно п) = O (п бревно п).

Псевдокод

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

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

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

(Поместите элементы 'a' в кучу по месту)процедура heapify (a, количество) является    (start присваивается индекс в 'a' последнего родительского узла)    (последний элемент в массиве, основанном на 0, имеет индекс count-1; найдите родительский элемент этого элемента)    начало ← iParent (count-1) пока начало ≥ 0 делать        (просейте узел с индексом 'start' в нужное место, чтобы все узлы ниже         начальный индекс находится в порядке кучи)        siftDown (a, начало, количество - 1) (перейти к следующему родительскому узлу)        начало ← начало - 1 (после просеивания корня все узлы / элементы находятся в порядке кучи)(Восстановите кучу, корневой элемент которой находится в индексе 'start', при условии, что кучи, основанные на ее дочерних элементах, действительны)процедура siftDown (a, начало, конец) является    корень ← начало пока iLeftChild (корень) ≤ конец делать    (Пока у рута есть хоть один потомок)        ребенок ← iLeftChild (корень) (Левый дочерний элемент корня)        поменять местами ← корень (Отслеживает ребенка, с которым можно поменяться местами)        если a [своп] тогда            поменять местами ← ребенок (Если есть правильный ребенок, и этот ребенок старше)        если ребенок + 1 ≤ конец и a [своп] тогда            поменять местами ← дочерний + 1 если swap = корень тогда            (Корень содержит самый большой элемент. Поскольку мы предполагаем, что кучи корнями в             дети действительны, это означает, что мы закончили.)            возвращаться        еще            swap (a [root], a [swap]) корень ← swap (повторите, чтобы продолжить просеивание ребенка сейчас)

В нагружать Процедуру можно представить как создание кучи снизу вверх путем последовательного просеивания вниз, чтобы установить куча собственности. Альтернативная версия (показанная ниже), которая строит кучу сверху вниз и просеивает вверх, может быть проще для понимания. Этот просеять версию можно представить как начало с пустой кучи и последовательную вставку элементов, тогда как siftDown Приведенная выше версия рассматривает весь входной массив как полную, но «сломанную» кучу и «ремонтирует» ее, начиная с последней нетривиальной подкучи (то есть с последнего родительского узла).

Разница во временной сложности между версией «siftDown» и версией «siftUp».

Так же siftDown версия heapify имеет О(п) временная сложность, в то время как просеять версия, приведенная ниже, имеет О(п бревно п) временная сложность из-за ее эквивалентности с вставкой каждого элемента по одному в пустую кучу.[4]Это может показаться нелогичным, поскольку, на первый взгляд, очевидно, что первый делает только половину обращений к своей функции логарифмического просеивания, чем второй; т.е. они кажутся различающимися только постоянным множителем, который никогда не влияет на асимптотический анализ.

Чтобы понять эту разницу в сложности, обратите внимание, что количество обменов, которые могут произойти во время любого одного вызова siftUp увеличивается с глубиной узла, на котором выполняется вызов. Суть в том, что существует намного (экспоненциально много) больше «глубоких» узлов, чем «мелких» узлов в куче, так что siftUp может иметь полное логарифмическое время работы на приблизительно линейном количестве вызовов, сделанных на узлах в или около "низа" кучи. С другой стороны, количество свопов, которые могут произойти во время одного вызова siftDown. уменьшается по мере увеличения глубины узла, на котором выполняется вызов. Таким образом, когда siftDown нагружать начинается и звонит siftDown на нижнем и наиболее многочисленных уровнях узлов каждый вызов просеивания будет включать в себя, самое большее, количество перестановок, равное «высоте» (от нижней части кучи) узла, на котором выполняется вызов просеивания. Другими словами, около половины вызовов siftDown будут иметь не более одного свопа, затем около четверти вызовов будут иметь не более двух свопов и т. Д.

Сам алгоритм heapsort имеет О(п бревно п) временная сложность с использованием любой из версий heapify.

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

Вариации

Конструкция кучи Флойда

Самым важным вариантом основного алгоритма, который включен во все практические реализации, является алгоритм построения кучи Флойда, который работает в О(п) время и использование отсеивание скорее, чем отсеивание, что позволяет избежать необходимости реализации siftup.

Вместо того, чтобы начинать с тривиальной кучи и многократно добавлять листья, алгоритм Флойда начинает с листьев, замечая, что они сами по себе тривиальные, но действительные кучи, а затем добавляет родителей. Начиная с элемента п/2 и работая в обратном направлении, каждый внутренний узел становится корнем допустимой кучи путем просеивания. Последний шаг - отсеивание первого элемента, после чего весь массив подчиняется свойству кучи.

Известно, что наихудшее число сравнений на этапе построения кучи Флойда в Heapsort равно 2п − 2s2(п) − е2(п), куда s2(п) это количество 1 бит в двоичном представлении п и е2(п) - количество завершающих 0 бит.[5]

Стандартная реализация алгоритма построения кучи Флойда вызывает большое количество промахи в кеше как только размер данных превышает размер Кэш процессора. Намного лучшую производительность на больших наборах данных можно получить путем слияния в глубину упорядочить, комбинируя вспомогательные кучи как можно скорее, а не объединяя все вспомогательные кучи на одном уровне, прежде чем переходить к предыдущему.[6][7]

Сортировка снизу вверх

Сортировка снизу вверх - это вариант, который значительно сокращает количество требуемых сравнений. В то время как обычная heapsort требует 2п бревно2п + О(п) сравнения в худшем случае и в среднем,[8] восходящий вариант требует п бревно2п + О(1) сравнения в среднем,[8] и 1.5п бревно2п + О(п) в худшем случае.[9]

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

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

Сортировка снизу вверх вместо этого находит путь от самых больших потомков к конечному уровню дерева (как если бы он вставлял -∞), используя только одно сравнение на уровень. Другими словами, он находит лист, обладающий тем свойством, что он и все его предки больше или равны своим братьям и сестрам. (При отсутствии одинаковых ключей этот лист является уникальным.) Затем с этого листа выполняется поиск вверх (с использованием одного сравнения на уровень) для правильной позиции в этом пути для вставки а[конец]. Это то же место, что и при обычном поиске методом heapsort, и для выполнения вставки требуется такое же количество обменов, но для поиска этого местоположения требуется меньше сравнений.[9]

Поскольку он идет полностью вниз, а затем возвращается вверх, он называется heapsort with bounce некоторыми авторами.[12]

функция leafSearch (a, i, конец) является    j ← я пока iRightChild (j) ≤ конец делать        (Определите, кто из двух детей j старший)        если a [iRightChild (j)]> a [iLeftChild (j)] тогда            j ← iRightChild (j) еще            j ← iLeftChild (j) (На последнем уровне может быть только один ребенок)    если iLeftChild (j) ≤ конец тогда        j ← iLeftChild (j) возвращаться j

Возвращаемое значение листПоиск используется в модифицированном siftDown рутина:[9]

процедура siftDown (а, я, конец) является    j ← leafSearch (a, i, end) пока a [i]> a [j] делать        j ← iParent (j) x ← a [j] a [j] ← a [i] пока j> я делать        поменять местами x, a [iParent (j)] j ← iParent (j)

Восходящая сортировка была объявлена ​​лучшей быстрой сортировкой (со средним выбором из трех точек поворота) для массивов размером ≥16000.[8]

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

Дальнейшее уточнение выполняет двоичный поиск на пути к выбранному листу и сортирует в худшем случае (п+1) (журнал2(п+1) + журнал2 бревно2(п+1) + 1.82) + О(бревно2п) сравнения, приближение теоретико-информационная нижняя оценка из п бревно2п − 1.4427п сравнения.[13]

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

Другие варианты

  • Тернарная сортировка[15] использует троичная куча вместо двоичной кучи; то есть у каждого элемента в куче есть три дочерних элемента. Его сложнее запрограммировать, но он выполняет в постоянное количество раз меньше операций подкачки и сравнения. Это связано с тем, что каждый шаг отсеивания в тернарной куче требует трех сравнений и одного обмена, тогда как в двоичной куче требуются два сравнения и один обмен. Два уровня в тройной крышке кучи 32 = 9 элементов, выполняя больше работы с тем же количеством сравнений, что и три уровня в двоичной куче, которые покрывают только 23 = 8.[нужна цитата ] Это в первую очередь представляет академический интерес, так как дополнительная сложность не стоит незначительной экономии, а восходящая сортировка в куче лучше обоих.
  • В гладкая сортировка алгоритм[16] это разновидность heapsort, разработанная Эдсгер Дейкстра в 1981 году. Как и heapsort, верхняя граница smoothsort О(п бревноп). Преимущество плавной сортировки в том, что она приближается к О(п) время, если ввод уже отсортирован до некоторой степени, в то время как heapsort усредняет О(п бревноп) независимо от исходного состояния сортировки. Из-за своей сложности гладкая сортировка используется редко.[нужна цитата ]
  • Левкопулос и Петерсон[17] описать вариант heapsort на основе кучи Декартовы деревья. Сначала строится декартово дерево из входных данных О(п) time, а его корень помещается в двоичную кучу из 1 элемента. Затем мы многократно извлекаем минимум из двоичной кучи, выводим корневой элемент дерева и добавляем его левый и правый дочерние элементы (если есть), которые сами являются декартовыми деревьями, в двоичную кучу.[18] Как они показывают, если входные данные уже почти отсортированы, декартовы деревья будут очень несбалансированными, с несколькими узлами, имеющими левые и правые дочерние элементы, в результате чего двоичная куча останется небольшой и позволит алгоритму сортировать быстрее, чем О(п бревноп) для входов, которые уже почти отсортированы.
  • Несколько вариантов, таких как слабая сортировка требовать пбревно2п+О(1) сравнения в худшем случае, близком к теоретическому минимуму, с использованием одного дополнительного бита состояния на узел. Хотя этот дополнительный бит делает алгоритмы некорректными, но если место для него можно найти внутри элемента, эти алгоритмы просты и эффективны,[6]:40 но все же медленнее, чем двоичные кучи, если сравнение ключей достаточно дешево (например, целочисленные ключи), поэтому постоянный коэффициент не имеет значения.[19]
  • «Непревзойденная куча сортировки» Катаянена не требует дополнительного хранилища, работает пбревно2п+О(1) сравнения и аналогичное количество перемещений элементов.[20] Однако это еще более сложно и неоправданно, если сравнение не очень дорогое.

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

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

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

Таким образом, из-за O (п бревно п) верхняя граница времени работы heapsort и постоянная верхняя граница его вспомогательной памяти, встроенные системы с ограничениями реального времени или системы, связанные с безопасностью, часто используют heapsort, например ядро ​​Linux.[21]

Heapsort также конкурирует с Сортировка слиянием, который имеет те же временные границы. Сортировка слиянием требует Ω (п) вспомогательное пространство, но для heapsort требуется только постоянное количество. На практике heapsort обычно работает быстрее на машинах с маленькими или медленными кеши данных, и не требует столько внешней памяти. С другой стороны, сортировка слиянием имеет несколько преимуществ перед heapsort:

  • Сортировка слиянием в массивах имеет значительно лучшую производительность кеширования данных, часто превосходящую по производительности heapsort на современных настольных компьютерах, поскольку сортировка слиянием часто обращается к смежным областям памяти (хорошо местонахождение ссылки ); Ссылки heapsort разбросаны по всей куче.
  • Heapsort - это не стабильная сортировка; Сортировка слиянием стабильна.
  • Сортировка слиянием распараллеливает хорошо и может достичь почти линейное ускорение с тривиальной реализацией; heapsort не является очевидным кандидатом на использование параллельного алгоритма.
  • Сортировку слиянием можно адаптировать для работы с по отдельности связанные списки с О (1) дополнительное пространство. Heapsort может быть адаптирован для работы на вдвойне связанные списки только с О (1) лишнее пространство наверху.[нужна цитата ]
  • Сортировка слиянием используется в внешняя сортировка; heapsort - нет. Местонахождение ссылки является проблемой.

Интросорт является альтернативой heapsort, которая сочетает быструю сортировку и heapsort, чтобы сохранить преимущества обоих: скорость heapsort наихудшего случая и средняя скорость быстрой сортировки.

Пример

Пусть {6, 5, 3, 1, 8, 7, 2, 4} будет списком, который мы хотим отсортировать от наименьшего к наибольшему. (ПРИМЕЧАНИЕ для шага «Создание кучи»: более крупные узлы не остаются ниже родителей меньших узлов. Они меняются местами с родителями, а затем рекурсивно проверяются, требуется ли еще один обмен, чтобы большие числа оставались выше меньших чисел в двоичном дереве кучи. .)

Пример на heapsort.
1. Создайте кучу
Кучанедавно добавленный элементпоменять местами элементы
ноль6
65
6, 53
6, 5, 31
6, 5, 3, 18
6, 5, 3, 1, 8 5, 8
6, 8, 3, 1, 56, 8
8, 6, 3, 1, 57
8, 6, 3, 1, 5, 73, 7
8, 6, 7, 1, 5, 32
8, 6, 7, 1, 5, 3, 24
8, 6, 7, 1, 5, 3, 2, 41, 4
8, 6, 7, 4, 5, 3, 2, 1
2. Сортировка
Кучапоменять местами элементыудалить элементотсортированный массивДетали
8, 6, 7, 4, 5, 3, 2, 18, 1поменяйте местами 8 и 1, чтобы удалить 8 из кучи
1, 6, 7, 4, 5, 3, 2, 88удалить 8 из кучи и добавить в отсортированный массив
1, 6, 7, 4, 5, 3, 21, 78поменяйте местами 1 и 7, так как они не в порядке в куче
7, 6, 1, 4, 5, 3, 21, 38поменяйте местами 1 и 3, поскольку они не в порядке в куче
7, 6, 3, 4, 5, 1, 27, 28поменяйте местами 7 и 2, чтобы удалить 7 из кучи
2, 6, 3, 4, 5, 1, 778удалить 7 из кучи и добавить в отсортированный массив
2, 6, 3, 4, 5, 12, 67, 8поменяйте местами 2 и 6, так как они не в порядке в куче
6, 2, 3, 4, 5, 12, 57, 8поменять местами 2 и 5, так как они не в порядке в куче
6, 5, 3, 4, 2, 16, 17, 8поменяйте местами 6 и 1, чтобы удалить 6 из кучи
1, 5, 3, 4, 2, 667, 8удалить 6 из кучи и добавить в отсортированный массив
1, 5, 3, 4, 21, 56, 7, 8поменять местами 1 и 5, так как они не в порядке в куче
5, 1, 3, 4, 21, 46, 7, 8поменяйте местами 1 и 4, поскольку они не в порядке в куче
5, 4, 3, 1, 25, 26, 7, 8поменяйте местами 5 и 2, чтобы удалить 5 из кучи
2, 4, 3, 1, 556, 7, 8удалить 5 из кучи и добавить в отсортированный массив
2, 4, 3, 12, 45, 6, 7, 8поменяйте местами 2 и 4, поскольку они не в порядке в куче
4, 2, 3, 14, 15, 6, 7, 8поменяйте местами 4 и 1, чтобы удалить 4 из кучи
1, 2, 3, 445, 6, 7, 8удалить 4 из кучи и добавить в отсортированный массив
1, 2, 31, 34, 5, 6, 7, 8поменяйте местами 1 и 3, поскольку они не в порядке в куче
3, 2, 13, 14, 5, 6, 7, 8поменяйте местами 3 и 1, чтобы удалить 3 из кучи
1, 2, 334, 5, 6, 7, 8удалить 3 из кучи и добавить в отсортированный массив
1, 21, 23, 4, 5, 6, 7, 8поменяйте местами 1 и 2, поскольку они не в порядке в куче
2, 12, 13, 4, 5, 6, 7, 8поменяйте местами 2 и 1, чтобы удалить 2 из кучи
1, 223, 4, 5, 6, 7, 8удалить 2 из кучи и добавить в отсортированный массив
112, 3, 4, 5, 6, 7, 8удалить 1 из кучи и добавить в отсортированный массив
1, 2, 3, 4, 5, 6, 7, 8завершенный

Примечания

  1. ^ Скиена, Стивен (2008). «Поиск и сортировка». Руководство по разработке алгоритмов. Springer. п. 109. Дои:10.1007/978-1-84800-070-4_4. ISBN  978-1-84800-069-8. [H] eapsort - это не что иное, как реализация сортировки по выбору с использованием правильной структуры данных.
  2. ^ Уильямс 1964
  3. ^ а б Брасс, Питер (2008). Расширенные структуры данных. Издательство Кембриджского университета. п. 209. ISBN  978-0-521-88037-4.
  4. ^ «Приоритетные очереди». Архивировано из оригинал 9 сентября 2020 г.. Получено 10 сентября 2020.
  5. ^ Сученек, Марек А. (2012), «Элементарный, но точный анализ наихудшего случая программы Флойда по строительству кучи», Fundamenta Informaticae, 120 (1): 75–92, Дои:10.3233 / FI-2012-751
  6. ^ а б Бойесен, Джеспер; Катаянен, Юрки; Спорк, Маз (2000). «Пример проектирования производительности: строительство кучи» (PostScript). ACM Журнал экспериментальной алгоритмики. 5 (15): 15 – es. CiteSeerX  10.1.1.35.3248. Дои:10.1145/351827.384257. S2CID  30995934. Альтернативный источник PDF.
  7. ^ Чен, Цзинсен; Эделькамп, Стефан; Элмасри, Амр; Катаянен, Юрки (27–31 августа 2012 г.). Построение кучи на месте с оптимизированными сравнениями, перемещениями и пропусками кеша (PDF). 37-я международная конференция "Математические основы информатики". Братислава, Словакия. С. 259–270. Дои:10.1007/978-3-642-32589-2_25. ISBN  978-3-642-32588-5. S2CID  1462216. См., В частности, рис.3.
  8. ^ а б c Вегенер, Инго (13 сентября 1993 г.). "ВЕРХНИЙ ВЕРХНИЙ СПОРТ, новый вариант HEAPSORT избиение, в среднем, БЫСТРЫЙ СОРТ (если п не очень маленький) " (PDF). Теоретическая информатика. 118 (1): 81–98. Дои:10.1016 / 0304-3975 (93) 90364-у. Хотя это переиздание работы, впервые опубликованной в 1990 году (на конференции «Математические основы компьютерных наук»), этот метод был опубликован Карлссоном в 1987 году.[13]
  9. ^ а б c Флейшер, Рудольф (февраль 1994). «Жесткая нижняя граница для худшего случая сортировки снизу вверх» (PDF). Алгоритмика. 11 (2): 104–115. Дои:10.1007 / bf01182770. HDL:11858 / 00-001M-0000-0014-7B02-C. S2CID  21075180. Также доступно как Флейшер, Рудольф (апрель 1991). Точная нижняя граница для наихудшего случая сортировки снизу вверх (PDF) (Технический отчет). MPI-INF. МПИ-И-91-104.
  10. ^ а б Мельхорн, Курт; Сандерс, Питер (2008). «Приоритетные очереди» (PDF). Алгоритмы и структуры данных: базовый набор инструментов. Springer. п. 142. ISBN  978-3-540-77977-3.
  11. ^ а б McDiarmid, C.J.H .; Рид, Б.А. (Сентябрь 1989 г.). "Быстро наращивать кучи" (PDF). Журнал алгоритмов. 10 (3): 352–365. Дои:10.1016/0196-6774(89)90033-3.
  12. ^ Морет, Бернар; Шапиро, Генри Д. (1991). «8.6 Heapsort». Алгоритмы от P до NP Том 1: Дизайн и эффективность. Бенджамин / Каммингс. п. 528. ISBN  0-8053-8008-6. За неимением лучшего названия мы называем эту расширенную программу «heapsort with bounce».'
  13. ^ а б Карлссон, Сканте (март 1987 г.). «Вариант heapsort с почти оптимальным количеством сравнений» (PDF). Письма об обработке информации. 24 (4): 247–250. Дои:10.1016/0020-0190(87)90142-6. S2CID  28135103.
  14. ^ Вегенер, Инго (Март 1992 г.). "Наихудшая сложность варианта МакДиармида и Рида ВЕРХНИЙ ВЕРХНИЙ СПОРТ меньше чем п бревноп + 1.1п". Информация и вычисления. 97 (1): 86–96. Дои:10.1016 / 0890-5401 (92) 90005-Z.
  15. ^ «Структуры данных, использующие Паскаль», 1991, стр. 405,[требуется полная цитата ][автор отсутствует ][ISBN отсутствует ] дает тройную сортировку в качестве студенческого упражнения. «Напишите процедуру сортировки, подобную heapsort, за исключением того, что она использует троичную кучу».
  16. ^ Дейкстра, Эдсгер В. Smoothsort - альтернатива сортировке на месте (EWD-796a) (PDF). Архив Э.В. Дейкстры.Центр американской истории, Техасский университет в Остине. (транскрипция )
  17. ^ Левкопулос, Христос; Петерссон, Ола (1989), «Heapsort - адаптировано для предварительно отсортированных файлов», WADS '89: Материалы семинара по алгоритмам и структурам данных, Конспект лекций по информатике, 382, Лондон, Великобритания: Springer-Verlag, стр. 499–509, Дои:10.1007/3-540-51542-9_41, ISBN  978-3-540-51542-5 Heapsort - адаптировано для предварительно отсортированных файлов. (Q56049336).
  18. ^ Шварц, Кейт (27 декабря 2010 г.). "CartesianTreeSort.hh". Архив интересного кода. Получено 5 марта 2019.
  19. ^ Катаянен, Юрки (23 сентября 2013 г.). В поисках очереди с наилучшим приоритетом: извлеченные уроки. Разработка алгоритмов (семинар 13391). Дагштуль. С. 19–20, 24.
  20. ^ Катаянен, Юрки (2–3 февраля 1998 г.). Окончательный Heapsort. Вычислительная техника: 4-й австралийский симпозиум по теории. Австралийские компьютерные науки коммуникации. 20 (3). Перт. С. 87–96.
  21. ^ https://github.com/torvalds/linux/blob/master/lib/sort.c Исходный код ядра Linux

Рекомендации

внешняя ссылка