Выбор ответа Middle Куча обновлено
Какую кучу взять
Вопрос
Нужно найти k точек, ближайших к началу координат. Какую кучу размера k использовать?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Max-кучу по расстоянию: вытесняем самую дальнюю. Ищем k наименьших, поэтому храним их в max-куче: вершина это худший кандидат, его сравниваем с новым и при необходимости заменяем.
Варианты ответа
- Max-кучу по расстоянию: вытесняем самую дальнююправильный ответ
- Min-кучу по расстоянию: в вершине ближайшая точка
- Любую: разницы нет, обе дают O(n log k)
- Кучу по координате x, ведь она дешевле расстояния
Разбор
Ищем k наименьших, поэтому храним их в max-куче: вершина это худший кандидат, его сравниваем с новым и при необходимости заменяем. Правило: «k наименьших → max-куча, k наибольших → min-куча». O(n log k).
- Min-куча размера k не позволит быстро выкинуть худшего (самого дальнего).
- Разница есть, как объяснено.
- Расстояние зависит от обеих координат, сравнивают x² + y² (корень не нужен).
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.