Пирамидальная сортировка превращает массив в двоичную max-кучу, а затем многократно переносит максимум в конец массива. Это редкая сортировка с гарантированным худшим случаем O(n log n), памятью O(1) и без рекурсии. Здесь куча — лишь инструмент для сортировки; саму структуру и модуль heapq разбирает урок кучи и heapq.

Max-куча: дерево и массив
Max-куча: дерево и массив

Куча в массиве

Max-куча — двоичное дерево, в котором каждый родитель не меньше детей; корень — максимум. Она хранится в массиве без указателей: дети i — это 2i + 1 и 2i + 2, родитель — (i - 1) // 2. Уровни дерева лежат в массиве подряд.

python
a = [10, 5, 7, 4, 1, 3, 2]
for i in range(len(a)):
    left, right = 2 * i + 1, 2 * i + 2
    parent = (i - 1) // 2
    kids = [a[k] for k in (left, right) if k < len(a)]
    print(i, a[i], "parent", a[parent] if i else None, "children", kids)

def is_max_heap(a):
    return all(a[(i - 1) // 2] >= a[i] for i in range(1, len(a)))

print(is_max_heap(a), is_max_heap([1, 5, 3]))
text
0 10 parent None children [5, 7]
1 5 parent 10 children [4, 1]
2 7 parent 10 children [3, 2]
3 4 parent 5 children []
4 1 parent 5 children []
5 3 parent 7 children []
6 2 parent 7 children []
True False

sift_down

sift_down(a, i, n) спускает узел i внутри кучи a[:n]: меняет его с большим из детей, пока он не станет не меньше своих детей. Время — высота кучи, O(log n).