Где применяется
1. Задача
В шаге 78 ты поднимался вверх по дереву и искал, где сходятся две ветви. Куча тоже дерево. Порядка в ней ровно столько, чтобы самое маленькое число всегда можно было взять сразу.
Задача такая. У тебя есть набор чисел, и он меняется. Снова и снова тебе нужно самое маленькое число из тех, что есть сейчас. А пока ты работаешь, в набор приходят новые числа.
Можно держать весь набор отсортированным. Но это лишняя работа: при каждой вставке приходится сдвигать элементы, чтобы новое число встало точно на своё место. Полный порядок тебе не нужен. Нужно одно: самое маленькое число всегда лежит там, где его можно прочитать за один шаг.
Куча (по-английски heap) делает ровно это. Ей не нужны узлы и ссылки между ними: она живёт в обычном массиве. В этом уроке ты соберёшь две её части: как дерево раскладывается по массиву и как вставить новое число.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
LeetCode редко просит отдельно вставку в кучу, поэтому эти задачи тренируют вторую половину урока, нумерацию дерева как массива. Родитель i стоит на (i минус 1) >> 1, дети на 2i + 1 и 2i + 2, и вопросы о форме дерева превращаются в арифметику. Задачи на кучу начинаются с урока 81.
Пронумеруй узлы так, как куча нумерует ячейки, и дерево полное, если наибольший номер равен числу узлов минус 1.
Дай каждому узлу его номер как в куче и меряй уровень как последний минус первый плюс 1, а на каждом уровне нумеруй заново с 0, чтобы числа не росли.
При нумерации как в куче родитель метки равен label >> 1, а зигзаг лишь отражает метку внутри её уровня.