🔴 Сложный ⏱️ 55 минут

Пирамидальная сортировка

📋 Содержание урока

Пирамидальная сортировка 🗻

Вспомни алгоритм Дейкстры из урока 263: на каждом шаге он должен мгновенно найти среди ещё не посещённых вершин ту, у которой сейчас наименьшая оценка расстояния. Если делать это линейным перебором по всем вершинам, получается $O(V^2)$ — на плотных графах приемлемо, но на разреженном графе с миллионами вершин и рёбер это катастрофически медленно. Ровно та же проблема «быстро достать самый приоритетный элемент, при этом постоянно добавляя новые» возникает в beam search — методе декодирования текста, которым языковая модель на каждом шаге генерации выбирает несколько наиболее вероятных продолжений из огромного множества кандидатов. И там, и там нужна структура данных, которая умеет две вещи одновременно и быстро: добавлять новый элемент и извлекать самый приоритетный из уже накопленных.

Именно эту структуру — двоичную кучу (binary heap) — ты разберёшь в этом уроке, а заодно и алгоритм сортировки, который на ней естественным образом строится: пирамидальную сортировку (heap sort). Куча — это не какая-то экзотика ради одной лишь сортировки: это рабочая лошадка, которая прячется внутри heapq в Python, внутри PriorityQueue в Java, внутри реализации алгоритма Дейкстры с приоритетной очередью, внутри планировщиков задач операционных систем и внутри той самой процедуры beam search, что генерирует текст в диалоговых языковых моделях прямо сейчас.

Heap sort завершает треугольник алгоритмов сортировки, который ты строишь три урока подряд. Быстрая сортировка из урока 267 в среднем очень быстра, но на неудачных данных скатывается к $O(n^2)$. Сортировка слиянием из урока 268 гарантирует $O(n\log n)$ в любом случае, но платит за это дополнительной памятью $O(n)$. Пирамидальная сортировка даёт третий вариант компромисса: гарантированная сложность $O(n\log n)$, как у merge sort, но при этом работает на месте, без единого дополнительного массива, — а цену за эту комбинацию платит устойчивостью, которую heap sort, в отличие от merge sort, не сохраняет.

В этом уроке ты разберёшься со структурой кучи и её компактным представлением через обычный массив без единого указателя, разберёшь операцию heapify — «просеивание» элемента вниз, которая восстанавливает свойство кучи, — и докажешь удивительный факт: построить кучу из произвольного массива можно не за $O(n\log n)$, как кажется на первый взгляд, а за линейное время $O(n)$. Дальше ты соберёшь из этих кирпичиков сам алгоритм сортировки и, наконец, увидишь кучу в её втором, не менее важном амплуа — как структуру данных приоритетной очереди, без которой не обходится ни эффективный алгоритм Дейкстры, ни beam search в современных языковых моделях.

История

Пирамидальную сортировку придумал Дж. У. Дж. Уильямс (J. W. J. Williams) и опубликовал в 1964 году в журнале Communications of the ACM под названием «Algorithm 232: Heapsort» — короткую заметку на неполную страницу, в которой был описан и сам алгоритм извлечения максимума из кучи, и способ построить кучу из произвольного массива. Название «heap» (куча) Уильямс выбрал осознанно: в отличие от полностью упорядоченной структуры, куча хранит лишь частичный, «слабый» порядок — достаточный, чтобы мгновенно найти самый большой элемент, но не более того, — что и делает операции над ней такими дешёвыми.

Уже в том же 1964 году другой классик информатики, Роберт У. Флойд (Robert W. Floyd) — тот самый, чьё имя носит алгоритм Флойда — Уоршелла из урока 264, — опубликовал усовершенствованный способ построения кучи прямо на месте, без дополнительной памяти, доказав, что эту операцию можно выполнить за линейное время $O(n)$, а не за $O(n\log n)$, как можно было бы наивно предположить. Именно связка «алгоритм Уильямса плюс построение кучи по Флойду» и стала тем каноническим heap sort, который сегодня разбирают в любом курсе алгоритмов.

Историческое значение heap sort выходит далеко за рамки одной лишь сортировки. До этой работы уже существовала идея приоритетной очереди как абстракции, но именно двоичная куча дала ей эффективную, компактную и легко реализуемую на реальном компьютере структуру данных — без указателей, без сбалансированных деревьев, всего лишь массив и три арифметические формулы для навигации по нему. Это сочетание простоты реализации и строгих гарантий по времени сделало кучу фундаментальным строительным блоком: сегодня она лежит в основе очередей с приоритетом в операционных системах, алгоритмов на графах вроде Дейкстры и Прима, сжатия Хаффмана и — что для тебя особенно актуально — механизмов декодирования в современных языковых моделях.

Структура кучи и представление через массив

Интуиция

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

«Почти полное бинарное дерево» здесь ключевое условие: все уровни дерева, кроме, может быть, последнего, заполнены полностью, а последний уровень заполняется слева направо без пропусков. Это не эстетическое требование, а инженерное: именно благодаря такой форме кучу можно хранить не в виде дерева с указателями на потомков, а в виде обычного плоского массива — без единого указателя, компактно и с отличной кэш-локальностью, — а переход от индекса узла к индексам его родителя и потомков вычисляется по формуле, а не по ссылке.

Алгоритм

Представление кучи через массив (нумерация индексов с нуля):

родитель элемента с индексом $i$: $\text{parent}(i) = \lfloor (i-1)/2 \rfloor$

левый потомок: $\text{left}(i) = 2i+1$

правый потомок: $\text{right}(i) = 2i+2$

Свойство max-heap: для любого индекса $i$, у которого есть потомки, выполняется $arr[i] \geq arr[\text{left}(i)]$ и $arr[i] \geq arr[\text{right}(i)]$ (для min-heap — неравенства в обратную сторону). Корень дерева — всегда элемент arr[0], и в max-heap это гарантированно наибольший элемент во всей структуре.

Листья дерева — это все индексы от $\lfloor n/2 \rfloor$ до $n-1$ включительно (при массиве длины $n$), поскольку у элемента с индексом $\lfloor n/2 \rfloor - 1$ (последнего внутреннего узла) потомки — это индексы $n-1$ и, возможно, $n$, а последний уже выходит за границу массива.

Разбор примеров

Пример 1 (лёгкий). Проверить, является ли массив [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] корректным max-heap.

Для индекса 0 (значение 16): left(0) = 1 (14), right(0) = 2 (10). 16 ≥ 14 и 16 ≥ 10 — свойство выполнено. Для индекса 1 (значение 14): left(1) = 3 (8), right(1) = 4 (7). 14 ≥ 8 и 14 ≥ 7 — выполнено. Для индекса 2 (значение 10): left(2) = 5 (9), right(2) = 6 (3). 10 ≥ 9 и 10 ≥ 3 — выполнено. Для индекса 3 (значение 8): left(3) = 7 (2), right(3) = 8 (4). 8 ≥ 2 и 8 ≥ 4 — выполнено. Для индекса 4 (значение 7): left(4) = 9 (1), правого потомка нет, так как right(4) = 10 уже выходит за границу массива длины 10. 7 ≥ 1 — выполнено. Индексы 5–9 — листья, потомков нет, проверять нечего.

Ответ: все внутренние узлы удовлетворяют свойству max-heap, массив корректен.

Пример 2 (средний). Проверить массив [3, 9, 5, 12, 8] — является ли он max-heap, и если нет, найти первое нарушение.

Для индекса 0 (значение 3): left(0) = 1 (9), right(0) = 2 (5). Требуется 3 ≥ 9 — это ложно. Свойство кучи нарушено уже в корне: родитель 3 меньше своего левого потомка 9.

Ответ: массив не является max-heap; нарушение — пара (индекс 0, значение 3) и (индекс 1, значение 9), где родитель меньше потомка. Такой массив нужно превратить в кучу операцией heapify — этим мы займёмся в следующем разделе.

Пример 3 (важный — поиск листьев). Для массива длины $n = 10$ определить, с какого индекса начинаются листья, и объяснить, почему именно с этого индекса.

По формуле $\lfloor n/2 \rfloor = \lfloor 10/2 \rfloor = 5$. Значит, индексы 5, 6, 7, 8, 9 — листья, а индексы 0, 1, 2, 3, 4 — внутренние узлы, у которых есть хотя бы один потомок. Проверим границу: у индекса 4 (последний внутренний узел) left(4) = 9 — это ещё существующий индекс массива, значит 4 действительно внутренний узел. У индекса 5 left(5) = 11 — это уже выходит за пределы массива длины 10, значит 5 — лист.

Ответ: листья начинаются с индекса $\lfloor n/2 \rfloor = 5$; это разбиение критично для следующего раздела, потому что операция heapify имеет смысл запускать только на внутренних узлах — у листьев потомков нет, и просеивать элемент вниз попросту некуда.

Почему это важно

Представление кучи через массив с формулами parent/left/right — это ровно та деталь, которая делает heap sort сортировкой на месте: сама куча в процессе работы алгоритма будет жить в том же массиве, который нужно отсортировать, без единого дополнительного массива под структуру дерева и без указателей, которые пришлось бы хранить отдельно для каждого узла. Именно компактность массива-представления кучи — прямая причина, по которой heap sort требует $O(1)$ дополнительной памяти, в отличие от сортировки слиянием с её обязательным буфером $O(n)$ из прошлого урока.

Heapify и построение кучи за O(n)

Интуиция

Представь, что у тебя почти правильная куча — оба поддерева некоторого узла уже удовлетворяют свойству кучи, но сам этот узел может нарушать его относительно своих детей. Достаточно сравнить значение узла с его потомками, и если один из потомков больше, поменять их местами — но после обмена узел, который только что «спустился» на позицию потомка, снова может нарушать свойство кучи уже там, поэтому сравнение и обмен нужно повторить рекурсивно, спускаясь дальше вниз, пока элемент не окажется на своём законном месте или не станет листом. Эта операция называется heapify или просеиванием вниз (sift-down) — она чинит ровно одно локальное нарушение свойства кучи, «протаскивая» неправильный элемент вниз по дереву.

Раз heapify умеет чинить одно нарушение в поддереве, при условии что оба его дочерних поддерева уже являются корректными кучами, то целую кучу из произвольного массива можно построить снизу вверх: пройтись по всем внутренним узлам в порядке от последнего к первому (то есть от глубоких узлов к корню) и вызвать heapify на каждом. К моменту, когда очередь доходит до узла, оба его поддерева гарантированно уже являются корректными кучами (они обработаны раньше, так как расположены глубже), а значит heapify корректно чинит именно этот узел. Листья трогать не нужно вовсе — у них нет потомков, свойство кучи для них выполняется автоматически.

Алгоритм

Heapify / sift-down(arr, n, i) — просеивание элемента с индексом i вниз в куче размера n:

Считать largest = i, left = 2i+1, right = 2i+2.

Если left < n и arr[left] > arr[largest], обновить largest = left.

Если right < n и arr[right] > arr[largest], обновить largest = right.

Если largest != i — обменять arr[i] и arr[largest] местами, затем рекурсивно вызвать sift_down(arr, n, largest) для «упавшего» на новую позицию элемента.

Если largest == i — свойство кучи в этом узле уже выполнено, остановиться.

Build-max-heap(arr) — построение кучи из произвольного массива за O(n):

Взять n = len(arr).

Пройтись по индексам i от $\lfloor n/2 \rfloor - 1$ (последний внутренний узел) до 0 включительно, в убывающем порядке.

На каждом шаге вызвать sift_down(arr, n, i).

def sift_down(arr, n, i):
    largest = i
    left, right = 2 * i + 1, 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        sift_down(arr, n, largest)


def build_max_heap(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, n, i)

Разбор примеров

Пример 1 (лёгкий — один вызов sift_down). Дан массив [4, 10, 3, 1, 2], у которого нарушение свойства кучи только в корне (оба поддерева уже корректны). Трассировать sift_down(arr, 5, 0).

i=0: largest=0, left=1 (10), right=2 (3). arr[1]=10 > arr[0]=4 → largest=1. arr[2]=3 > arr[1]=10? Нет, 3 < 10 → largest остаётся 1. largest(1) != i(0) → меняем местами arr[0] и arr[1]: массив становится [10, 4, 3, 1, 2]. Рекурсивный вызов sift_down(arr, 5, 1): largest=1, left=3 (1), right=4 (2). arr[3]=1 > arr[1]=4? Нет. arr[4]=2 > arr[1]=4? Нет. largest == i → остановка.

Ответ: [10, 4, 3, 1, 2] — корректная max-heap, элемент 4 просел на один уровень вниз, элемент 10 встал на своё законное место в корне.

Пример 2 (средний — построение кучи с нуля). Построить max-heap из массива [1, 3, 5, 4, 2, 7, 6] (7 элементов, индексы 0–6).

Последний внутренний узел: $\lfloor 7/2 \rfloor - 1 = 2$. Цикл идёт по i = 2, 1, 0.

i=2 (значение 5): left=5 (7), right=6 (6). 7 > 5 → largest=5. 6 > 7? Нет. Меняем arr[2] и arr[5]: [1, 3, 7, 4, 2, 5, 6]. Рекурсия в sift_down(arr, 7, 5): left=11 — за границей, листьев нет, останов.

i=1 (значение 3): left=3 (4), right=4 (2). 4 > 3 → largest=3. 2 > 4? Нет. Меняем arr[1] и arr[3]: [1, 4, 7, 3, 2, 5, 6]. Рекурсия sift_down(arr, 7, 3): left=7 — за границей, останов.

i=0 (значение 1): left=1 (4), right=2 (7). 4 > 1 → largest=1. 7 > 4 → largest=2. Меняем arr[0] и arr[2]: [7, 4, 1, 3, 2, 5, 6]. Рекурсия sift_down(arr, 7, 2): left=5 (5), right=6 (6). 5 > 1 → largest=5. 6 > 5 → largest=6. Меняем arr[2] и arr[6]: [7, 4, 6, 3, 2, 5, 1]. Рекурсия sift_down(arr, 7, 6): left=13 — за границей, останов.

Ответ: итоговая куча [7, 4, 6, 3, 2, 5, 1]. Проверка: 7≥4, 7≥6 (корень), 4≥3, 4≥2 (узел 1), 6≥5, 6≥1 (узел 2) — свойство max-heap выполнено во всех внутренних узлах.

Пример 3 (важный — почему построение кучи стоит O(n), а не O(n log n)). Оценить суммарную стоимость build_max_heap для кучи из $n = 15$ элементов (высота дерева — 3, четыре уровня узлов: корень на высоте 3, затем высоты 2, 1, 0).

Ключевое наблюдение: стоимость одного вызова sift_down для узла пропорциональна не глубине узла от корня, а его высоте — расстоянию до самого дальнего листа в его поддереве, поскольку именно столько шагов элемент может «упасть» вниз. На высоте $h=0$ (листья) — их 8, стоимость каждого вызова $O(0)$ (листья вообще не обрабатываются циклом). На высоте $h=1$ — таких узлов 4, каждый требует не более 1 шага сравнения-обмена. На высоте $h=2$ — таких узлов 2, каждый требует не более 2 шагов. На высоте $h=3$ (корень) — 1 узел, требует не более 3 шагов. Суммарная стоимость: $4\cdot 1 + 2\cdot 2 + 1\cdot 3 = 4 + 4 + 3 = 11$ — величина, сравнимая с $n=15$, а не с $n\log n \approx 15\cdot 4 = 60$.

В общем виде для кучи из $n$ элементов число узлов на высоте $h$ не превышает $\lceil n/2^{h+1}\rceil$, а стоимость обработки каждого такого узла — $O(h)$. Суммируя по всем высотам от $0$ до $\log_2 n$, получаем ряд $\sum_h h \cdot n/2^{h+1}$, который сходится к $O(n)$ — потому что подавляющее большинство узлов кучи (половина всех узлов) — это листья на высоте 0, которые вообще не требуют работы, а узлов с большой высотой (где просеивание может пройти много шагов) экспоненциально мало.

Ответ: построение кучи из $n$ элементов стоит $O(n)$, а не $O(n\log n)$, потому что дорогие вызовы sift_down (высокие узлы, близкие к корню) встречаются экспоненциально редко, а частые вызовы (низкие узлы, близкие к листьям) почти ничего не стоят.

Почему это важно

Линейность построения кучи — не просто красивый факт, а необходимое условие того, чтобы heap sort в целом уложился в $O(n\log n)$: если бы построение кучи стоило $O(n\log n)$ (как это было бы при наивной вставке элементов по одному через sift-up), общая сложность сортировки не изменилась бы асимптотически, поскольку сам этап извлечения тоже даёт $O(n\log n)$ — но при работе с реальными системами, где константы имеют значение, разница между «дешёвым построением плюс дорогое извлечение» и «дорогим построением плюс дорогое извлечение» ощутима на практике. К тому же сам факт — что операция, интуитивно кажущаяся $n\log n$-й, на самом деле линейна, — важный урок анализа алгоритмов: суммировать стоимости по узлам дерева нужно с учётом их фактического распределения по высотам, а не полагаться на «на глаз» оценку через глубину каждого узла.

Алгоритм сортировки

Интуиция

В max-heap корень — это всегда наибольший элемент во всей структуре, и найти его стоит $O(1)$. Идея heap sort прямая: построй max-heap из всего массива, затем повторяй одну и ту же процедуру — забери текущий максимум (корень) и помести его на своё окончательное место в конец ещё не отсортированной части массива, поменяв местами с последним элементом кучи; после этого «сожми» кучу на один элемент (последний элемент больше в куче не участвует — он уже на своём финальном месте) и восстанови свойство кучи для нового корня через sift_down. Повтори это $n-1$ раз, и массив окажется полностью отсортирован по возрастанию — причём весь процесс происходит в том же самом массиве, без единого дополнительного контейнера под данные.

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

Алгоритм

Heap sort(arr):

Вызвать build_max_heap(arr), чтобы весь массив стал корректной max-heap. Стоимость — $O(n)$.

Для end от n-1 до 1 (включительно, с шагом -1):

Поменять местами arr[0] (текущий максимум, корень кучи) и arr[end] (последняя позиция ещё не отсортированной части).

Вызвать sift_down(arr, end, 0) — восстановить свойство кучи для нового корня, при этом куча теперь имеет размер end (элемент на позиции end и правее уже в отсортированной части и в куче больше не участвует).

После завершения цикла массив arr отсортирован по возрастанию на месте.

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(arr, end, 0)
    return arr

Разбор примеров

Пример 1 (лёгкий). Полная трассировка heap_sort([4, 10, 3, 5, 1]).

Построение кучи. $n=5$, последний внутренний узел — индекс 1. i=1 (значение 10): left=3 (5), right=4 (1). 5 > 10? Нет. 1 > 10? Нет. Без изменений. i=0 (значение 4): left=1 (10), right=2 (3). 10 > 4 → largest=1. 3 > 10? Нет. Меняем arr[0] и arr[1]: [10, 4, 3, 5, 1]. Рекурсия sift_down(arr, 5, 1): left=3 (5), right=4 (1). 5 > 4 → largest=3. 1 > 5? Нет. Меняем arr[1] и arr[3]: [10, 5, 3, 4, 1]. Куча построена: [10, 5, 3, 4, 1].

Извлечение, end=4. Меняем arr[0] и arr[4]: [1, 5, 3, 4, 10]. sift_down(arr, 4, 0): left=1 (5), right=2 (3). 5 > 1 → largest=1. 3>5? Нет. Меняем arr[0] и arr[1]: [5, 1, 3, 4, 10]. Рекурсия sift_down(arr,4,1): left=3 (4). 4>1 → largest=3. Меняем arr[1] и arr[3]: [5, 4, 3, 1, 10].

Извлечение, end=3. Меняем arr[0] и arr[3]: [1, 4, 3, 5, 10]. sift_down(arr,3,0): left=1 (4), right=2 (3). 4>1→largest=1. 3>4? Нет. Меняем arr[0] и arr[1]: [4, 1, 3, 5, 10].

Извлечение, end=2. Меняем arr[0] и arr[2]: [3, 1, 4, 5, 10]. sift_down(arr,2,0): left=1 (1), right за границей (n=2). 1>3? Нет. Без изменений.

Извлечение, end=1. Меняем arr[0] и arr[1]: [1, 3, 4, 5, 10]. sift_down(arr,1,0): у кучи размера 1 потомков нет, останов.

Ответ: [1, 3, 4, 5, 10] — массив отсортирован по возрастанию, ни один дополнительный массив за всё время работы не выделялся.

Пример 2 (средний). Тот же исходный массив, что и в примере 2 из урока про merge sort — [38, 27, 43, 3, 9, 82, 10], — чтобы можно было сравнить ход работы двух разных алгоритмов на одинаковых данных.

Построение кучи. $n=7$, последний внутренний узел — индекс 2. i=2 (43): left=5 (82), right=6 (10). 82>43→largest=5. Меняем arr[2], arr[5]: [38,27,82,3,9,43,10]. Рекурсия на 5 — потомков нет (left=11), останов. i=1 (27): left=3 (3), right=4 (9). Оба меньше 27, без изменений. i=0 (38): left=1 (27), right=2 (82). 82>38→largest=2. Меняем arr[0],arr[2]: [82,27,38,3,9,43,10]. Рекурсия sift_down(arr,7,2): left=5(43), right=6(10). 43>38→largest=5. Меняем arr[2],arr[5]: [82,27,43,3,9,38,10]. Куча построена: [82,27,43,3,9,38,10].

Извлечения (кратко, по результату каждого шага). end=6: меняем arr[0],arr[6] → [10,27,43,3,9,38,82], sift_down даёт [43,27,38,3,9,10,82]. end=5: меняем arr[0],arr[5] → [10,27,38,3,9,43,82], sift_down даёт [38,27,10,3,9,43,82]. end=4: меняем arr[0],arr[4] → [9,27,10,3,38,43,82], sift_down даёт [27,9,10,3,38,43,82]. end=3: меняем arr[0],arr[3] → [3,9,10,27,38,43,82], sift_down даёт [10,9,3,27,38,43,82]. end=2: меняем arr[0],arr[2] → [3,9,10,27,38,43,82], sift_down даёт [9,3,10,27,38,43,82]. end=1: меняем arr[0],arr[1] → [3,9,10,27,38,43,82], sift_down тривиален.

Ответ: [3, 9, 10, 27, 38, 43, 82] — тот же результат, что дала сортировка слиянием в уроке 268, но полученный совершенно другой механикой и без единого дополнительного массива.

Пример 3 (важный — гарантия для любого входа). Отсортировать уже отсортированный по убыванию массив [9, 7, 5, 3, 1] и показать, что heap sort не деградирует и не ускоряется на «удобном» входе, в отличие от вставками или пузырьком.

Массив [9, 7, 5, 3, 1] уже является корректной max-heap (проверка: 9≥7, 9≥5 для корня; 7≥3, 7≥1 для узла 1) — построение кучи не потребует ни одного обмена. Но дальше начинаются извлечения, и каждое из них всё равно требует полноценного sift_down, потому что после обмена корня с последним элементом кучи свойство почти наверняка нарушается заново: end=4: меняем arr[0],arr[4] → [1,7,5,3,9], sift_down: left=1(7)→largest=1, right=2(5)<7, меняем → [7,1,5,3,9], рекурсия на 1: left=3(3)>1→largest=3, меняем → [7,3,5,1,9]. end=3: меняем arr[0],arr[3] → [1,3,5,7,9], sift_down: left=1(3),right=2(5)→largest=2, меняем → [5,3,1,7,9]. end=2: меняем arr[0],arr[2] → [1,3,5,7,9], sift_down: left=1(3)→largest=1, меняем → [3,1,5,7,9]. end=1: меняем arr[0],arr[1] → [1,3,5,7,9], тривиально.

Ответ: [1, 3, 5, 7, 9] — тот факт, что исходный массив уже был отсортирован (пусть и в обратном порядке, что само по себе делает его валидной кучей), не избавил алгоритм ни от одного полноценного вызова sift_down на этапе извлечения: число операций порядка $n\log n$ одинаково для любого входа, что и составляет главную гарантию heap sort.

Почему это важно

Heap sort даёт ровно ту же гарантию худшего случая $O(n\log n)$, что и merge sort, но достигает её принципиально иначе — без вспомогательной памяти. Это делает heap sort привлекательным выбором именно там, где важны одновременно и предсказуемость времени работы, и жёсткие ограничения по памяти: встроенные системы, ядра операционных систем, среды, где выделение динамической памяти во время выполнения ограничено или вовсе запрещено. Расплатой за эту комбинацию оказывается устойчивость — heap sort постоянно переставляет далёкие друг от друга элементы массива обменами, и относительный порядок элементов с одинаковыми ключами теряется почти всегда, что мы разберём в заданиях ниже.

Приоритетная очередь как применение

Интуиция

Куча — это не только «внутренности» алгоритма сортировки, а самостоятельная абстрактная структура данных — приоритетная очередь (priority queue): коллекция, которая поддерживает вставку произвольного элемента и извлечение элемента с наивысшим приоритетом, причём обе операции стоят $O(\log n)$. Сравни это с более простыми альтернативами: неотсортированный список даёт вставку за $O(1)$, но извлечение максимума требует полного перебора — $O(n)$; отсортированный список даёт извлечение максимума мгновенно, $O(1)$, но вставка нового элемента в нужную позицию требует сдвига — снова $O(n)$. Куча — это компромисс, который не бьёт рекорд ни в одной из двух операций по отдельности, но держит обе на уровне $O(\log n)$ одновременно, и именно эта сбалансированность делает её незаменимой всюду, где вставки и извлечения чередуются в произвольном порядке, а не идут одним пакетом, как при сортировке.

Вставка нового элемента в кучу работает зеркально к heapify: новый элемент добавляется в конец массива (следующая свободная позиция листа), а затем просеивается вверх (sift-up) — сравнивается с родителем, и если он больше родителя (для max-heap), меняется с ним местами, и так до тех пор, пока не займёт корректное место. Извлечение максимума устроено так же, как один шаг heap sort: взять корень, поменять его местами с последним элементом, уменьшить размер кучи на единицу, просеять новый корень вниз.

Алгоритм

Insert(heap, value) — вставка в кучу, O(log n):

Добавить value в конец массива-кучи (heap.append(value)), n = len(heap), индекс нового элемента i = n - 1.

Пока i > 0 и heap[parent(i)] < heap[i] (нарушение свойства max-heap с родителем): поменять heap[i] и heap[parent(i)] местами, i = parent(i).

Повторять шаг 2, пока свойство кучи не восстановится или элемент не дойдёт до корня.

Extract-max(heap) — извлечение максимума, O(log n):

Сохранить heap[0] как результат.

Переместить последний элемент массива на позицию корня: heap[0] = heap.pop().

Если куча не пуста, вызвать sift_down(heap, len(heap), 0), чтобы восстановить свойство кучи.

Вернуть сохранённый результат.

В Python модуль heapq реализует именно min-heap (наименьший элемент — на вершине), и его функции heappush и heappop выполняют ровно insert и extract-min за $O(\log n)$:

import heapq

pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
smallest = heapq.heappop(pq)  # вернёт 1 — наименьший элемент

Разбор примеров

Пример 1 (алгоритм Дейкстры с приоритетной очередью). Вспомни граф из урока 263: без приоритетной очереди на каждой итерации Дейкстра ищет непосещённую вершину с минимальной оценкой расстояния линейным перебором по всем вершинам — $O(V)$ на итерацию, итого $O(V^2)$ для всего алгоритма. С min-heap вместо линейного перебора каждая вершина попадает в кучу как пара (расстояние, вершина) при обновлении оценки (релаксации ребра), а извлечение вершины с минимальной оценкой — это просто heappop. Пусть на некотором шаге куча содержит [(2, 'B'), (5, 'C'), (7, 'D')] (уже в виде корректной min-heap по первому элементу пары). heappop вернёт (2, 'B') за $O(\log 3)$ вместо перебора всех троих. Если после обработки B релаксация обновит оценку вершины D до 4, новая пара (4, 'D') добавляется в кучу через heappush за $O(\log n)$ — куча сама разберётся, куда её поставить, без пересортировки всей структуры.

Ответ: переход от линейного перебора к min-heap меняет сложность одной итерации Дейкстры с $O(V)$ на $O(\log V)$, а итоговую сложность всего алгоритма — с $O(V^2)$ на $O((V+E)\log V)$, что на разреженных графах (типичных для дорожных сетей, социальных графов, семантических графов знаний) — разница на порядки при больших $V$.

Пример 2 (beam search в языковой модели). Модель генерирует текст пошагово, и на каждом шаге нужно удержать только $k$ (ширина луча, например $k=3$) наиболее вероятных частичных последовательностей, отбросив всё остальное, — иначе число кандидатов растёт экспоненциально с длиной генерируемой последовательности. Пусть на очередном шаге уже накоплены три кандидата с их логарифмами вероятности: heap = [(-0.5, "the cat"), (-1.2, "the dog"), (-0.9, "a cat")] (используем min-heap с отрицательными логарифмами вероятности, чтобы «наименее вероятный» кандидат всплывал на вершину и его было легко удалить, когда куча переполняется). Модель предлагает нового кандидата (-0.3, "the cats"), более вероятного, чем все три текущих. Вставляем его: heappush добавляет пару в кучу за $O(\log 3)$. Теперь в куче четыре элемента, а нужно оставить только три — выполняем heappop, который снимает пару с наименьшим приоритетом (в данном случае с наибольшим по модулю отрицательным логарифмом, то есть наименее вероятную) — это (-1.2, "the dog").

Ответ: после вставки и одного извлечения куча содержит трёх лучших кандидатов: "the cats", "the cat", "a cat", а менее вероятный "the dog" отброшен — и вся операция «удержать top-k при непрерывном потоке новых кандидатов» стоит $O(\log k)$ на каждого кандидата благодаря куче, а не $O(k)$ или $O(k\log k)$, как при поддержании отсортированного списка или пересортировке на каждом шаге.

Пример 3 (top-k без полной сортировки через heapq). Дан поток из миллиона чисел, нужно найти три наибольших, не сортируя весь массив. Наивный способ — sorted(stream)[-3:] стоит $O(n\log n)$. Правильный способ — держать min-heap размера ровно k=3: для первых трёх чисел просто наполнить кучу; для каждого следующего числа сравнить его с минимумом кучи (heap[0]), и если новое число больше — вытолкнуть минимум и вставить новое (heapq.heapreplace), иначе проигнорировать. Пусть первые три числа потока — [4, 9, 2], куча после построения: [2, 9, 4] (min-heap, корень — минимум 2). Приходит 7: 7 > heap[0]=2 → заменяем: heapreplace удаляет 2, добавляет 7, куча становится [4, 9, 7]. Приходит 1: 1 > heap[0]=4? Нет — игнорируем. Приходит 15: 15 > 4 → заменяем 4 на 15, куча [7, 9, 15].

Ответ: после обработки всего потока в куче размера 3 останутся три наибольших встреченных числа, а стоимость всей операции — $O(n\log k)$ вместо $O(n\log n)$ при полной сортировке, что при $k \ll n$ (например, $k=10$ против $n=10^6$) — разница на порядки; функция heapq.nlargest(k, stream) в Python делает ровно это под капотом.

Почему это важно

Приоритетная очередь на основе кучи — это именно тот мост, который связывает тему сортировки с темами графовых алгоритмов и с современными системами обработки последовательностей. В алгоритме Дейкстры (урок 263) куча превращает квадратичную сложность в почти линейную на разреженных графах — практическая необходимость для любой системы маршрутизации или поиска кратчайшего пути в графе знаний. В beam search куча (или её функциональный эквивалент) — это ровно тот механизм, который позволяет языковой модели на каждом шаге генерации отбрасывать подавляющее большинство маловероятных продолжений, сохраняя вычислительный бюджет для по-настоящему конкурентных вариантов, вместо того чтобы держать в памяти экспоненциально растущее дерево всех возможных последовательностей.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Для массива длины n = 12 (индексация с нуля) вычислить индексы родителя, левого и правого потомка для элемента с индексом 5.

Задание 2: Проверить, является ли массив [20, 15, 18, 5, 10, 12, 8] корректной max-heap.

Задание 3: Для массива длины n = 21 определить, с какого индекса начинаются листья.

Задание 4: Выполнить один вызов sift_down для массива [2, 8, 9, 1, 3], где нарушение только в корне.

Задание 5: Почему build_max_heap начинает цикл с индекса $\lfloor n/2\rfloor - 1$, а не с индекса 0 или с последнего индекса n-1?

Задание 6: Сколько дополнительной памяти (сверх исходного массива) требует heap_sort для массива из миллиона элементов?

Задание 7: Является ли heap sort устойчивой сортировкой? Обосновать одним предложением.

Задание 8: Заполнить пропуск: построение кучи из n элементов стоит ___, а не $O(n\log n)$, как можно было бы наивно предположить.

Задание 9: Массив [5, 5, 5, 5] (все элементы равны) уже пройден через build_max_heap. Сколько операций потребует извлечение всех четырёх элементов через heap_sort?

Задание 10: Заполнить таблицу: указать сложность вставки и извлечения максимума для (а) неотсортированного массива, (б) отсортированного массива, (в) двоичной кучи.

Средние задания (11–20)

Задание 11: Полностью выполнить build_max_heap для массива [2, 7, 26, 25, 19, 17, 1, 90, 3, 36] (10 элементов) и указать итоговую кучу.

Задание 12: Продолжить пример из задания 11: выполнить полный heap_sort над кучей [90, 36, 26, 25, 19, 17, 1, 7, 3, 2] и указать первые три извлечённых значения (первые три шага цикла извлечения).

Задание 13: Для $n = 31$ элемента (полное бинарное дерево высотой 4) посчитать суммарную стоимость build_max_heap по формуле $\sum_h h\cdot\lceil n/2^{h+1}\rceil$ для $h=0..4$ и сравнить с $n\log_2 n$.

Задание 14: Реализовать функцию sift_down на Python (без подсматривания в текст урока).

Задание 15: Для сортировки по убыванию (вместо возрастания) какую кучу нужно использовать в heap_sort — max-heap или min-heap? Обосновать.

Задание 16: Найти третий по величине элемент массива [12, 3, 45, 7, 19, 2, 30], не сортируя весь массив, используя min-heap размера 3.

Задание 17: Привести конкретный пример пары равных по ключу элементов, порядок которых меняется местами после heap_sort (демонстрация неустойчивости).

Задание 18: Заполнить таблицу компромиссов: для quicksort, merge sort и heap sort указать худшее время и требуемую дополнительную память.

Задание 19: Дан наивный алгоритм Дейкстры без кучи со сложностью $O(V^2)$. Оценить сложность с min-heap для графа с $V=10^5$ вершинами и $E=5\times10^5$ рёбрами.

Задание 20: Объяснить, почему для приоритетной очереди с постоянным чередованием вставок и извлечений (а не разовой сортировкой всего набора данных сразу) куча предпочтительнее, чем сортировка всего набора один раз и последующий линейный проход.

Продвинутые задания (21–30)

Задание 21: Реализовать полную функцию heap_sort на Python, используя build_max_heap и sift_down.

Задание 22: Реализовать класс MaxPriorityQueue с методами insert и extract_max, используя массив-кучу и sift_down/sift_up.

Задание 23: Используя min-heap, реализовать k-way merge для слияния трёх отсортированных списков A=[1,7], B=[2,4,9], C=[3,5] (та же задача, что решалась в уроке 268 про merge sort, но теперь через явную кучу).

Задание 24: Реализовать функцию top_k(stream, k), находящую k наибольших элементов потока чисел за $O(n\log k)$ с помощью min-heap размера k.

Задание 25: Смоделировать один шаг beam search с шириной луча $k=2$: текущие кандидаты (лог-вероятности) [(-0.4, "я иду"), (-1.1, "я бегу")], модель предлагает продолжения с добавленными лог-вероятностями (-0.6, "я иду домой"), (-0.9, "я иду гулять"), (-1.3, "я бегу быстро"). Какие два кандидата останутся после шага?

Задание 26: Реализовать алгоритм Дейкстры с приоритетной очередью heapq для графа, заданного списком смежности.

Задание 27: Почему на практике heap sort часто проигрывает quicksort по реальной скорости работы на массивах, помещающихся в оперативную память, несмотря на одинаковую асимптотику $O(n\log n)$ в среднем случае у quicksort?

Задание 28: Что такое introsort и почему он использует одновременно все три алгоритма из этого блока курса — quicksort, heap sort и сортировку вставками?

Задание 29: Спроектировать (план, без полной реализации) выбор алгоритма сортировки для встроенной системы с жёстким лимитом памяти 4 КБ и требованием предсказуемого времени отклика (сортируется массив из 2000 чисел).

Задание 30: Спроектировать систему планирования задач: есть поток задач с приоритетами, поступающих в произвольные моменты времени, и обработчик, который должен всегда брать в работу задачу с наивысшим приоритетом среди уже поступивших. Как здесь использовать кучу, и почему единоразовая сортировка всех задач не подходит?

Частые ошибки

Ошибка 1. Путают, какую кучу строить для возрастающей сортировки — думают, что для получения массива по возрастанию нужен min-heap (по аналогии «маленькое — в начало»).

Как выглядит: реализация строит min-heap и извлекает минимумы, помещая их в начало ещё не отсортированной части, что требует сдвига всех элементов и ломает саму идею in-place сортировки.

Почему возникает: интуитивно кажется, что раз итоговый порядок — по возрастанию, значит и куча должна быть «по возрастанию», то есть min-heap.

Как правильно: для возрастающей сортировки строится max-heap, а извлечённые максимумы кладутся не в начало, а в конец массива, освобождая место в начале для оставшейся кучи — именно так работает канонический heap sort.

Ошибка 2. Забывают уменьшать размер кучи (heap size) на каждой итерации извлечения и вызывают sift_down на всём массиве, включая уже отсортированный хвост.

Как выглядит: цикл извлечения не передаёт в sift_down уменьшающийся параметр end, а всегда использует полную длину массива n, из-за чего уже отсортированные (финальные) элементы в конце массива снова попадают в сравнения и портятся.

Почему возникает: легко забыть, что «куча» и «отсортированная часть» делят один и тот же массив, и что граница между ними должна явно сдвигаться параметром размера кучи, а не подразумеваться.

Как правильно: передавать в sift_down текущий размер активной кучи (end, уменьшающийся на каждой итерации), а не фиксированную длину всего массива.

Ошибка 3. Выполняют обмен корня с последним элементом кучи, но забывают вызвать sift_down после обмена.

Как выглядит: массив после серии обменов оказывается перемешанным, а не отсортированным, потому что после каждого обмена новый корень почти всегда нарушает свойство кучи, и без восстановления этого свойства следующий «максимум» на вершине оказывается вовсе не максимумом.

Почему возникает: обмен местами — заметное, «видимое» действие, а вызов sift_down после него легко воспринять как отдельный, необязательный шаг, а не неотъемлемую часть одной операции извлечения.

Как правильно: всегда рассматривать «извлечение максимума» как неделимую пару действий — обмен плюс немедленное восстановление свойства кучи через sift_down для нового корня.

Ошибка 4. Путают формулы индексов между 0-индексацией и 1-индексацией массива.

Как выглядит: используется формула parent(i) = i // 2, left(i) = 2i, right(i) = 2i+1 (верная для массива, пронумерованного с единицы), применительно к массиву, пронумерованному с нуля — из-за чего индексы съезжают, а свойство кучи вычисляется неправильно.

Почему возникает: многие классические учебники по алгоритмам используют 1-индексацию для простоты формул, тогда как реальные языки программирования вроде Python нумеруют массивы с нуля.

Как правильно: для 0-индексации использовать parent(i) = (i-1)//2, left(i) = 2i+1, right(i) = 2i+2 — и проверять эти формулы на маленьком конкретном примере перед тем, как использовать в реализации.

Ошибка 5. Считают heap sort устойчивой сортировкой по аналогии с merge sort, не проверив это допущение.

Как выглядит: heap sort используется для многоключевой сортировки (сначала по одному полю, потом по другому) в расчёте на устойчивость, а результат оказывается неправильным — порядок внутри групп с одинаковым вторым ключом не сохраняется.

Почему возникает: оба алгоритма дают гарантию $O(n\log n)$ в худшем случае, и легко по инерции перенести и остальные свойства merge sort на heap sort, не проверив их индивидуально.

Как правильно: для задач, где устойчивость критична (многоключевая сортировка, сохранение исходного порядка «равных» записей), выбирать merge sort или явно устойчивую реализацию, а не heap sort.

Ошибка 6. Строят кучу наивной вставкой элементов по одному через sift_up, считая это единственным способом, и не подозревают о более эффективном bottom-up построении через sift_down.

Как выглядит: код инициализирует пустую кучу и вызывает insert для каждого из n элементов исходного массива по очереди.

Почему возникает: операция вставки в кучу интуитивно понятнее и на первый взгляд кажется единственным способом «наполнить» структуру данных.

Как правильно: если весь набор данных известен заранее (что почти всегда так при подготовке к сортировке), строить кучу за $O(n)$ проходом build_max_heap снизу вверх, а не за $O(n\log n)$ последовательными вставками — асимптотика всего heap sort от этого не изменится (доминирует этап извлечения), но разница в константах и в понимании настоящей эффективности алгоритма значительна.

Главное запомнить

Куча (heap) — почти полное бинарное дерево со свойством кучи: каждый родитель не слабее (max-heap) или не сильнее (min-heap) своих потомков, при этом порядок между «братскими» поддеревьями не гарантирован.
Куча компактно хранится в обычном массиве без указателей: для индекса i (0-индексация) родитель — $\lfloor(i-1)/2\rfloor$, левый потомок — $2i+1$, правый — $2i+2$.
Heapify (sift_down) чинит одно локальное нарушение свойства кучи, «просеивая» элемент вниз по дереву за $O(\log n)$, при условии что оба дочерних поддерева уже являются корректными кучами.
Построение кучи из произвольного массива (build_max_heap) стоит удивительно мало — $O(n)$, а не $O(n\log n)$, потому что дорогие вызовы sift_down на узлах большой высоты встречаются экспоненциально редко.
Heap sort повторяет $n-1$ раз одну операцию: обменять корень (текущий максимум) с последней позицией активной кучи, уменьшить размер кучи на единицу, восстановить свойство кучи через sift_down — итоговая сложность $O(n\log n)$.
Гарантия $O(n\log n)$ у heap sort верна для любого входа без исключений, как и у merge sort, — в отличие от быстрой сортировки с её $O(n^2)$ в худшем случае.
В отличие от merge sort, heap sort работает на месте, требуя лишь $O(1)$ дополнительной памяти (не считая стека рекурсии), — цена этой экономии в том, что heap sort не устойчив.
Куча — не только инструмент сортировки, а самостоятельная структура данных приоритетной очереди с вставкой и извлечением приоритетного элемента за $O(\log n)$ каждая — компромисс, недостижимый ни отсортированным, ни неотсортированным массивом по отдельности.
Приоритетная очередь на куче лежит в основе эффективного алгоритма Дейкстры (снижает сложность с $O(V^2)$ до $O((V+E)\log V)$) и в основе beam search в языковых моделях, где на каждом шаге генерации нужно удерживать top-k наиболее вероятных продолжений.
Introsort (std::sort в C++) объединяет все три алгоритма блока — начинает как quicksort ради средней скорости, переключается на heap sort при слишком глубокой рекурсии ради гарантии худшего случая, и использует сортировку вставками на маленьких подмассивах.

Связь с темами курса

Что нужно было знать до этого урока

Этот урок завершает треугольник алгоритмов сортировки, начатый в уроке 266 (обзор видов сортировок) и продолженный уроками 267 (быстрая сортировка, стратегия «разделяй и властвуй» с непредсказуемым худшим случаем) и 268 (сортировка слиянием, гарантированная сложность ценой дополнительной памяти). Также напрямую используется алгоритм Дейкстры из урока 263 — именно неэффективный линейный перебор без приоритетной очереди, разобранный там, находит здесь своё естественное улучшение через кучу. Нотация $O(\cdot)$ из урока 251 нужна для формального анализа сложности heapify и построения кучи.

Что изучить дальше

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

Где это нужно в жизни

🤖 ML/AI и инженерия данных. Приоритетная очередь на куче — прямой строительный блок эффективного алгоритма Дейкстры (маршрутизация, графы знаний) и beam search (декодирование текста в языковых моделях, машинный перевод) — оба нуждаются в постоянном «добавь кандидата — забери лучший», для чего куча спроектирована изначально.

🐍 Языки программирования. Модуль heapq в Python и класс PriorityQueue/binary-heap в Java реализуют приоритетную очередь именно как двоичную кучу; introsort в основе std::sort в C++ переключается на heap sort всякий раз, когда quicksort рискует деградировать до $O(n^2)$, гарантируя тем самым, что стандартная сортировка C++ никогда формально не превышает $O(n\log n)$.

🗄️ Системы и базы данных. Операции нахождения top-k строк по некоторому критерию (ORDER BY ... LIMIT k) в СУБД и аналитических системах часто реализуются через кучу размера $k$ вместо полной сортировки всего набора данных — это даёт $O(n\log k)$ вместо $O(n\log n)$, что критично при больших $n$ и маленьком $k$.

⚙️ Встроенные и real-time системы. Там, где память жёстко ограничена, а время отклика должно быть предсказуемым (авионика, медицинское оборудование, контроллеры реального времени), heap sort — предпочтительный выбор именно потому, что одновременно даёт гарантию худшего случая $O(n\log n)$ и работу без дополнительной памяти, чего не может дать ни quicksort, ни merge sort по отдельности.

Интересные факты

Алгоритм впервые опубликован Дж. У. Дж. Уильямсом в 1964 году в Communications of the ACM под названием «Algorithm 232: Heapsort» — заметка занимала меньше страницы журнального текста, но задала структуру данных, без которой сегодня немыслима значительная часть алгоритмов на графах.
В том же 1964 году Роберт У. Флойд — тот самый автор алгоритма Флойда — Уоршелла из урока 264 — предложил способ построить кучу из произвольного массива за линейное время $O(n)$ прямо на месте, без дополнительной памяти; именно эта деталь и делает классический heap sort по-настоящему in-place алгоритмом.
Introsort, предложенный Дэвидом Массером в 1997 году и лежащий в основе std::sort в стандартной библиотеке C++, буквально использует все три алгоритма сортировки из этого блока курса одновременно: быструю сортировку как основной режим, heap sort как аварийный план при слишком глубокой рекурсии, и сортировку вставками для маленьких подмассивов.
Куча — основа классического алгоритма построения кода Хаффмана (оптимального префиксного кода для сжатия данных): на каждом шаге алгоритм извлекает из min-heap два наименее частых символа, объединяет их в новый «псевдосимвол» с суммарной частотой и снова кладёт в кучу — ровно тот же паттерн «извлечь минимум, обработать, возможно вставить обратно», что используется в приоритетных очередях повсюду.
Несмотря на теоретически такую же асимптотику $O(n\log n)$, что и у quicksort в среднем случае, heap sort на практике почти всегда работает медленнее из-за плохой кэш-локальности: узлы кучи, соседние в логическом дереве, могут быть далеко разнесены в физической памяти при больших индексах.

Лайфхаки

В реальном коде не реализуй свою кучу с нуля ради практических задач — используй встроенный heapq в Python (min-heap из коробки); для max-heap просто храни в куче отрицательные значения и инвертируй знак при извлечении.
Когда нужны только top-k элементов из большого массива или потока, никогда не сортируй всё целиком — держи min-heap размера k и получай $O(n\log k)$ вместо $O(n\log n)$; в Python это heapq.nlargest(k, iterable) или heapq.nsmallest(k, iterable).
Не путай стоимость построения кучи через n вставок ($O(n\log n)$) со стоимостью build_max_heap снизу вверх ($O(n)$) — если весь набор данных известен заранее, всегда используй второй способ.
Если задача требует одновременно жёсткого лимита памяти и гарантированного худшего времени выполнения, heap sort — первый кандидат среди трёх алгоритмов этого блока курса, а не quicksort (риск $O(n^2)$) и не merge sort (обязательный буфер $O(n)$).
Для любой задачи вида «постоянно приходят новые элементы вперемешку с запросами на извлечение самого приоритетного» — планировщик задач, симуляция дискретных событий, Дейкстра, beam search — сразу думай в терминах приоритетной очереди на куче, а не «накопить всё и отсортировать один раз».
Перед тем как полагаться на heap sort для многоключевой сортировки, вспомни, что он не устойчив, — если нужен сохранённый порядок «равных» элементов, используй merge sort или явно устойчивую реализацию, а не heap sort.

Три урока подряд — быстрая сортировка, сортировка слиянием и пирамидальная сортировка — на самом деле рассказывают одну историю с тремя разными концовками: как достичь $O(n\log n)$, и чем за это приходится платить. Quicksort платит риском деградации до $O(n^2)$ ради скорости на практике и экономии памяти. Merge sort платит дополнительной памятью $O(n)$ ради гарантии худшего случая и устойчивости. Heap sort платит устойчивостью ради той же гарантии худшего случая, но уже без лишней памяти. Ни один из трёх вариантов не «лучше» остальных вообще — каждый выигрывает ровно там, где важны именно его гарантии, и настоящее умение работать с алгоритмами — это не запомнить один «правильный» ответ, а понимать, какой из трёх компромиссов нужен именно в твоей задаче. А куча, помимо роли в сортировке, оказывается куда более универсальным инструментом — приоритетной очередью, которая будет снова и снова всплывать в курсе, от эффективных графовых алгоритмов до механизмов генерации текста в языковых моделях. Дальше тебя ждёт динамическое программирование — новая парадигма, которая учит решать задачи не разбиением на независимые куски, а переиспользованием уже посчитанного.

Понял тему? Закрепи в боте! 🚀

Попрактикуйся на задачах и получи персональные рекомендации от AI

💪 Начать тренировку

💬 Нашёл ошибку или есть вопрос по уроку? Написать в Telegram →