How it works?

Бинарная куча располагается в обычном массиве. Для узла с индексом i (начиная с 0), его дочерние элементы находятся по индексам 2*i + 1 и 2*i + 2. Эта индексация — основной прием, позволяющий дереву существовать внутри массива.

Пошаговый процесс:

1. Построение max-heap (максимальной кучи): перестройте массив так, чтобы каждый родитель был >= своих дочерних элементов. Наибольшее значение окажется по индексу 0.
2. Извлечение максимума: поменяйте местами корень (наибольший элемент) с последним элементом кучи, затем уменьшите размер кучи на единицу, чтобы наибольший элемент остался в конце в своей окончательной отсортированной позиции.
3. Восстановление с помощью просеивания вниз (sift-down): новый корень может оказаться не на своем месте, поэтому просейте его вниз (меняйте местами с его бóльшим дочерним элементом, повторяйте), пока свойство кучи не восстановится.
4. Повторяйте, пока куча не опустеет. Теперь массив отсортирован по возрастанию.

Пример на [4, 10, 3, 5, 1]:

• Построение max-heap: [10, 5, 3, 4, 1].
• Переместите корень 10 в конец и выполните просеивание вниз, затем повторите для 5, 4, 3.
• Результат: [1, 3, 4, 5, 10].