Сортировка кучей: алгоритм и варианты реализации

Введение

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

В информатике, heapsort — это алгоритм сортировки, основанный на сравнении, который можно рассматривать как «реализацию сортировки выбором с использованием подходящей структуры данных». Как и сортировка выбором, heapsort разделяет входные данные на отсортированную и неотсортированную области и итеративно уменьшает неотсортированную область, извлекая из неё наибольший элемент и вставляя его в отсортированную область. В отличие от сортировки выбором, heapsort не тратит время на линейный просмотр неотсортированной области; вместо этого heapsort поддерживает неотсортированную область в виде структуры данных куча, чтобы эффективно находить наибольший элемент на каждом шаге. Хотя на практике на большинстве машин он несколько медленнее, чем хорошо реализованная быстрая сортировка, он обладает преимуществами очень простой реализации и более благоприятным временем выполнения в худшем случае. Большинство практических вариантов быстрой сортировки включают реализацию heapsort в качестве резервного варианта, если они обнаруживают, что быстрая сортировка вырождается. Heapsort — это алгоритм сортировки на месте, но он не является стабильным. Heapsort был изобретён Дж. В. Дж. Уильямсом в 1964 году. В той же статье была представлена бинарная куча как полезная структура данных сама по себе. В том же году Роберт В. Флойд опубликовал улучшенную версию, которая могла сортировать массив на месте, продолжая свои предыдущие исследования алгоритма treesort.

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

Тройная сортировка кучи использует тройную кучу вместо двоичной кучи; то есть каждый элемент в куче имеет три дочерних элемента. Её сложнее программировать, но она выполняет на постоянное количество раз меньше операций обмена и сравнения. Это происходит потому, что каждый шаг просеивания вниз в тройной куче требует три сравнения и один обмен, в то время как в двоичной куче требуется два сравнения и один обмен. Два уровня в тройной куче охватывают 3^2 = 9 элементов, выполняя больший объем работы с тем же количеством сравнений, что и три уровня в двоичной куче, которые охватывают только 2^3 = 8. Это представляет в основном академический интерес или может служить упражнением для студентов, поскольку дополнительная сложность не оправдывает незначительной экономии, а сортировка кучи снизу вверх превосходит обе. Сортировка кучи с оптимизацией памяти улучшает локальность ссылок сортировки кучи, ещё больше увеличивая количество дочерних элементов. Это увеличивает количество сравнений, но поскольку все дочерние элементы хранятся последовательно в памяти, уменьшается количество строк кэша, к которым обращаются при обходе кучи, что приводит к повышению производительности. Стандартная реализация алгоритма построения кучи Флойда вызывает большое количество промахов кэша, когда размер данных превышает размер кэша процессора. Лучшую производительность на больших наборах данных можно получить, объединяя в глубину, объединяя подкучи как можно скорее, а не объединяя все подкучи на одном уровне, прежде чем переходить к следующему. Сортировка кучи вне области улучшает сортировку кучи снизу вверх, устраняя наихудший случай, гарантируя n log₂n + O(n) сравнений. Когда извлекается максимум, вместо заполнения освободившегося места несортированным значением данных, заполните его значением −∞, которое никогда не "подпрыгнет" обратно. Оказывается, что это можно использовать как примитив в алгоритме "QuickHeapsort" на месте (и нерекурсивном). Сначала выполните проход разделения, подобный быстрой сортировке, но измените порядок разделенных данных в массиве. Предположим (без потери общности), что меньший раздел больше, чем опорный элемент, который должен быть в конце массива, но наш шаг обратного разделения помещает его в начало. Сформируйте кучу из меньшего раздела и выполните на нём сортировку кучи вне области, обменивая извлеченные максимумы со значениями с конца массива. Они меньше опорного элемента, то есть меньше любого значения в куче, поэтому служат значениями −∞. После завершения сортировки кучи (и перемещения опорного элемента непосредственно перед теперь отсортированным концом массива) порядок разделов был изменен, и больший раздел в начале массива можно отсортировать тем же способом. (Поскольку нет хвостовой рекурсии, это также устраняет использование стека O(log n) быстрой сортировкой.) Алгоритм smoothsort — это вариант сортировки кучи, разработанный Эдсгером В. Дейкстрой в 1981 году. Как и у сортировки кучи, верхняя граница smoothsort — O(n log n). Преимущество smoothsort заключается в том, что он приближается ко времени O(n), если вход уже частично отсортирован, в то время как сортировка кучи в среднем имеет сложность O(n log n), независимо от начального состояния сортировки. Из-за своей сложности smoothsort используется редко. Левкопулос и Петерсон описывают вариант сортировки кучи, основанный на куче картезианских деревьев. Сначала из входных данных строится картезианское дерево за время O(n), и его корень помещается в двоичную кучу из 1 элемента. Затем мы многократно извлекаем минимум из двоичной кучи, выводим корневой элемент дерева и добавляем его левых и правых дочерних элементов (если они есть), которые сами являются картезианскими деревьями, в двоичную кучу. Как они показывают, если вход уже почти отсортирован, картезианские деревья будут очень несбалансированными, с небольшим количеством узлов, имеющих левых и правых дочерних элементов, в результате чего двоичная куча останется небольшой, и алгоритм сможет сортировать быстрее, чем O(n log n) для уже почти отсортированных входных данных. Несколько вариантов, таких как слабая сортировка кучи, требуют n log₂n + O(1) сравнений в наихудшем случае, что близко к теоретическому минимуму, используя один дополнительный бит состояния на узел. Хотя этот дополнительный бит делает алгоритмы не совсем на месте, если для него можно найти место внутри элемента, эти алгоритмы просты и эффективны, но все же медленнее, чем двоичные кучи, если сравнения ключей достаточно дешевы (например, целочисленные ключи), чтобы постоянный фактор не имел значения. "Окончательная сортировка кучи" Катаайнена не требует дополнительного хранилища, выполняет n log₂n + O(1) сравнений и аналогичное количество перемещений элементов. Однако она ещё более сложна и не оправдана, если сравнения очень дороги.

Ternary heapsort uses a ternary heap instead of a binary heap; that is, each element in the heap has three children. It is more complicated to program, but does a constant number of times fewer swap and comparison operations. This is because each sift down step in a ternary heap requires three comparisons and one swap, whereas in a binary heap two comparisons and one swap are required. Two levels in a ternary heap cover 32 = 9 elements, doing more work with the same number of comparisons as three levels in the binary heap, which only cover 23 = 8. This is primarily of academic interest, or as a student exercise, as the additional complexity is not worth the minor savings, and bottom up heapsort beats both. Memory optimized heapsort improves heapsort's locality of reference by increasing the number of children even more. This increases the number of comparisons, but because all children are stored consecutively in memory, reduces the number of cache lines accessed during heap traversal, a net performance improvement. The standard implementation of Floyd's heap construction algorithm causes a large number of cache misses once the size of the data exceeds that of the CPU cache. Better performance on large data sets can be obtained by merging in depth first order, combining subheaps as soon as possible, rather than combining all subheaps on one level before proceeding to the one above. Out of place heapsort improves on bottom up heapsort by eliminating the worst case, guaranteeing n log2n + O(n) comparisons. When the maximum is taken, rather than fill the vacated space with an unsorted data value, fill it with a −∞ sentinel value, which never "bounces" back up. It turns out that this can be used as a primitive in an in place (and non recursive) "QuickHeapsort" algorithm. First, you perform a quicksort like partitioning pass, but reversing the order of the partitioned data in the array. Suppose (without loss of generality) that the smaller partition is the one greater than the pivot, which should go at the end of the array, but our reversed partitioning step places it at the beginning. Form a heap out of the smaller partition and do out of place heapsort on it, exchanging the extracted maxima with values from the end of the array. These are less than the pivot, meaning less than any value in the heap, so serve as −∞ sentinel values. Once the heapsort is complete (and the pivot moved to just before the now sorted end of the array), the order of the partitions has been reversed, and the larger partition at the beginning of the array may be sorted in the same way. (Because there is no non tail recursion, this also eliminates quicksort's O(log n) stack usage.) The smoothsort algorithm is a variation of heapsort developed by Edsger W. Dijkstra in 1981. Like heapsort, smoothsort's upper bound is O(n log n). The advantage of smoothsort is that it comes closer to O(n) time if the input is already sorted to some degree, whereas heapsort averages O(n log n) regardless of the initial sorted state. Due to its complexity, smoothsort is rarely used. Levcopoulos and Petersson describe a variation of heapsort based on a heap of Cartesian trees. First, a Cartesian tree is built from the input in O(n) time, and its root is placed in a 1 element binary heap. Then we repeatedly extract the minimum from the binary heap, output the tree's root element, and add its left and right children (if any) which are themselves Cartesian trees, to the binary heap. As they show, if the input is already nearly sorted, the Cartesian trees will be very unbalanced, with few nodes having left and right children, resulting in the binary heap remaining small, and allowing the algorithm to sort more quickly than O(n log n) for inputs that are already nearly sorted. Several variants such as weak heapsort require n log2 n+O(1) comparisons in the worst case, close to the theoretical minimum, using one extra bit of state per node. While this extra bit makes the algorithms not truly in place, if space for it can be found inside the element, these algorithms are simple and efficient, but still slower than binary heaps if key comparisons are cheap enough (e. g. integer keys) that a constant factor does not matter. Katajainen's "ultimate heapsort" requires no extra storage, performs n log2 n+O(1) comparisons, and a similar number of element moves. It is, however, even more complex and not justified unless comparisons are very expensive.

Пример

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