Алгоритм: Найти k ближайших точек

Решение: k ближайших точек к origin

Задача

Даны точки на 2D плоскости и начало координат (origin). Найти K ближайших точек используя heap.

Решение: Max-Heap O(n log k)

Ключевая идея:

• Вместо вычисления евклидова расстояния можно сравнивать квадраты расстояний (избегаем sqrt)
• Используем max-heap размером K: храним K ближайших точек
• Для каждой точки: если расстояние меньше максимального в heap → заменяем

import heapq
from typing import List

def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
    """
    Найти k ближайших точек к origin (0, 0).
    Time: O(n log k), Space: O(k)
    """
    
    max_heap = []
    
    for point in points:
        # Квадрат расстояния (избегаем sqrt)
        dist_sq = point[0] ** 2 + point[1] ** 2
        
        if len(max_heap) < k:
            heapq.heappush(max_heap, (-dist_sq, point))
        elif dist_sq < -max_heap[0][0]:
            heapq.heapreplace(max_heap, (-dist_sq, point))
    
    return [point for dist, point in max_heap]

Примеры

points = [[1,3], [-2,2]]
k = 1
result = kClosest(points, k)  # [[-2, 2]]

points = [[3,3], [5,-1], [-2,4]]
k = 2
result = kClosest(points, k)  # [[3,3], [-2,4]]

Анализ сложности

Time: O(n log k)

• Итерация по n точкам: O(n)
• Каждая push/replace: O(log k)
• Извлечение: O(k log k)
• Итого: O(n log k)

Space: O(k)

• Heap хранит k точек

Почему heap лучше сортировки:

• Heap: O(n log k) время, O(k) память
• Сортировка: O(n log n) время, O(n) память
• При k << n это значительное ускорение

Альтернатива: Quickselect O(n) в среднем

Использует partitioning как в QuickSort, но останавливается на k-м элементе. Быстрее в среднем, но более сложная реализация.

Сравнение подходов

Практическое применение

• KNN классификация: k ближайших соседей
• Рекомендации: k похожих товаров
• Геолокация: k ближайших POI
• Кластеризация: поиск соседних точек
• Поиск по изображениям: k похожих изображений

Ключевые оптимизации

1. Используй квадрат расстояния (избегаешь sqrt)
2. Max-heap хранит только k элементов (экономит память)
3. Сравни с максимумом в куче (не со всеми точками)
4. Quickselect для O(n) если k очень мало