Код Senior Реализация с нуля обновлено
Двоичная куча
Условие
createHeap(compare): push, pop (наименьший по compare), peek, size. Все операции кроме peek за O(log n).
Что проверяют тесты
отдаёт по возрастанию
свой компаратор
пустая куча
дубликаты
много элементов
Как подойти
Массив вместо узлов и ссылок: индексная арифметика заменяет всю работу с указателями. Инвариант - родитель не хуже обоих детей. Куча нужна там, где надо многократно доставать минимум из меняющегося набора: top-K за O(n log k), слияние k списков, планировщики задач, алгоритм Дейкстры. В JS её нет в стандартной библиотеке, поэтому и просят написать.
Подсказки: 3
- Куча хранится в массиве: дети узла i лежат на 2i+1 и 2i+2, родитель - на (i-1)/2.
- push кладёт в конец и всплывает вверх, pop берёт корень и опускает последний элемент.
- При опускании сравнивай с обоими детьми и меняйся с лучшим.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.