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

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

Так что же определяет кучу? Вот несколько критериев:

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

Ниже мы продемонстрируем «сортировку кучи» с использованием максимальной кучи, выполнив несколько шагов:

  1. Мы с несортированным массивом. Мы берем этот массив и превращаем его в максимальную кучу, следуя правилам, упомянутым выше. Это можно сделать с помощью одной функции (в зависимости от языка), это может выглядеть примерно так: buildMaxHeap.
  2. Теперь, когда у нас есть массив в максимальном формате кучи, мы уверены, что наибольшее значение находится в корневом узле кучи. На этом этапе куча может быть не полностью отсортирована, но, следуя правилам максимальной кучи, по крайней мере каждый родительский узел в нашей куче будет больше, чем любой дочерний узел. Теперь мы переместим наибольшее значение (которое сейчас находится в корневом узле) в конец кучи, заменив его последним элементом.
  3. Наибольшее значение теперь должно находиться в последнем узле кучи. Мы знаем, что это правильная позиция (то есть теперь она отсортирована), поэтому мы можем удалить этот элемент из кучи. Теперь проблема заключается в том, что значение, которое мы поменяли на корневой узел, не вышло из строя. Чтобы исправить это, мы можем использовать функцию сортировки, часто называемую heapify, которая поможет нам изменить порядок оставшихся узлов в их «правильном» порядке в соответствии с правилами кучи. И мы будем продолжать делать эти 3 шага, пока не будет отсортирован каждый узел.

Примерно так и работает сортировка кучей!