Где применяется
1. Задача
Шаг 81 дал тебе два хода. Первый строит кучу из любого массива за один проход, O(n). Второй снимает с вершины наименьшее значение. Пирамидальная сортировка (heapsort) получается, если снимать минимум снова и снова, пока куча не опустеет.
У тебя массив чисел, и их нужно расставить по возрастанию. Ты уже умеешь быстро забирать наименьшее число из кучи. Забери его и запиши. Забери новое наименьшее и запиши. Повторяй. Когда куча опустела, записанные числа идут по порядку.
Это и есть весь метод: новой структуры данных и хитрых сравнений нет, ты берёшь построенную кучу и опустошаешь её. Пирамидальная сортировка стоит O(n log n) даже в худшем случае. А её классический вариант сортирует прямо внутри исходного массива и не берёт памяти под второй массив. Поэтому её выбирают там, где памяти мало, а медленные случаи недопустимы.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи, где значения нужны по порядку или нужны только первые несколько. Пирамидальная сортировка сортирует на месте за O(n log n) даже в худшем случае, а остановка после k извлечений даёт k наименьших.
Пирамидальная сортировка проходит без рекурсии и без лишнего массива и никогда не падает до n^2, как неаккуратная быстрая сортировка.
Построй кучу из пар число солдат и номер строки, потом извлеки k раз.
Построй макс-кучу и извлеки дважды, полная сортировка ради двух значений не нужна.