lab07 — куча и top-K¶

Бинарная куча на массиве, реализованная вручную (без heapq), приоритетная очередь поверх неё и задача top-K — найти K самых больших элементов, не сортируя весь массив. Это структура, на которой стоят планировщики и таймеры: куча умеет за O(log n) отдавать «самый срочный» элемент, а вставлять новые — тоже за O(log n).

Главная идея: дерево не нужно хранить ссылками и узлами — его можно «закодировать» индексами обычного массива.

Куча на массиве: арифметика индексов¶

Для элемента с индексом i:

Что	Индекс
родитель	`(i - 1) // 2`
левый потомок	`2*i + 1`
правый потомок	`2*i + 2`

Массив [1, 3, 2, 7, 5, 4] читается как дерево:

        1            индексы:        0
       / \                         / \
      3   2                       1   2
     / \  |                      / \  |
    7  5  4                     3  4  5

Свойство кучи (heap property): в min-куче каждый родитель не больше своих потомков (на вершине — минимум), в max-куче — наоборот. Это не полный порядок: соседи между собой не упорядочены, поэтому куча дешевле полной сортировки.

Класс BinaryHeap параметризован видом ("min" / "max") и работает через единственный компаратор — чтобы не дублировать просеивание под два случая:

def _higher(self, a, b) -> bool:
    # выше тот, кто должен быть ближе к вершине
    if self._kind == "min":
        return a < b   # min-куча: выше меньший
    return a > b       # max-куча: выше больший

Просеивание вверх (`sift_up`) — для push¶

Новый элемент кладём в конец массива и поднимаем, меняя местами с родителем, пока он «выше» родителя. Путь до корня — высота дерева, то есть O(log n).

def _sift_up(self, i: int) -> None:
    while i > 0:
        parent = (i - 1) // 2
        if self._higher(self._data[i], self._data[parent]):
            self._data[i], self._data[parent] = self._data[parent], self._data[i]
            i = parent
        else:
            break

Просеивание вниз (`sift_down`) — для pop¶

При pop вершину меняем с последним элементом, отрезаем вершину с конца, а новый корень опускаем: на каждом шаге выбираем потомка, который должен стоять выше, и меняемся с ним, пока свойство кучи нарушено. Тоже O(log n).

def _sift_down(self, i: int) -> None:
    n = array_length(self._data)
    while True:
        left, right = 2 * i + 1, 2 * i + 2
        best = i
        if left < n and self._higher(self._data[left], self._data[best]):
            best = left
        if right < n and self._higher(self._data[right], self._data[best]):
            best = right
        if best == i:
            break
        self._data[i], self._data[best] = self._data[best], self._data[i]
        i = best

Построение кучи из массива за `O(n)`¶

Наивно можно n раз вызвать push — это O(n log n). Но есть приём дешевле: просеять вниз все внутренние узлы, начиная с последнего родителя (n // 2 - 1) к корню. Суммарная работа — O(n) (большинство узлов сидят у самого низа и просеиваются на 1–2 уровня).

def _build(self, data: list) -> None:
    self._data = list(data)
    i = array_length(self._data) // 2 - 1
    while i >= 0:
        self._sift_down(i)
        i -= 1

Сложности¶

Операция	Сложность	Комментарий
`peek`	`O(1)`	вершина — это `data[0]`
`push`	`O(log n)`	sift_up по высоте дерева
`pop`	`O(log n)`	sift_down по высоте дерева
`build` (heapify)	`O(n)`	дешевле, чем `n × push`
heapsort	`O(n log n)`	build + `n` pop

Heapsort — прямое доказательство, что куча отдаёт элементы по порядку: последовательные pop из min-кучи дают возрастающую последовательность, из max-кучи — убывающую.

def heap_sort(arr: list, reverse: bool = False) -> list:
    heap = BinaryHeap(kind="max" if reverse else "min", data=arr)
    result = []
    while not heap.is_empty():
        result.append(heap.pop())
    return result

Приоритетная очередь¶

Поверх кучи строится приоритетная очередь: каждый элемент кладётся с числовым приоритетом, а очередь отдаёт самый срочный. В кучу кладётся кортеж (priority, seq, item):

priority — по нему идёт основное сравнение;
seq — монотонный счётчик вставок, tie-breaker: при равных приоритетах сравнение уходит на порядковый номер, очередь становится FIFO-стабильной;
item — сам элемент, который благодаря seq никогда не участвует в сравнении (поэтому элементами могут быть даже несравнимые объекты вроде dict).

pq = PriorityQueue(order="max")
pq.push("backup", 1)
pq.push("deploy-hotfix", 10)
pq.push("rotate-logs", 3)
pq.pop()   # -> "deploy-hotfix" (приоритет 10)

top-K без полной сортировки¶

Чтобы найти K самых больших элементов, не нужно сортировать весь массив за O(n log n). Держим min-кучу размера K: на её вершине — самый слабый из текущих лидеров. Идём по массиву один раз: пока в куче меньше K элементов — кладём; дальше, если очередной элемент больше вершины, выкидываем вершину и кладём новый.

def top_k_largest(arr: list, k: int) -> list:
    if k <= 0:
        return []
    heap = BinaryHeap(kind="min")
    for value in arr:
        if len(heap) < k:
            heap.push(value)
        elif value > heap.peek():
            heap.pop()
            heap.push(value)
    collected = []
    while not heap.is_empty():
        collected.append(heap.pop())
    collected.reverse()   # pop из min-кучи даёт возрастание
    return collected

Сложность — O(n log K), память — O(K). Когда K << n (top-10 из миллиона), это радикально дешевле полной сортировки (O(n log n), память O(n)). top_k_smallest — зеркало на max-куче размера K.

Краевые случаи: k <= 0 → пустой список; k >= len(arr) → возвращаются все элементы (в нужном порядке).

Где это в проде¶

Планировщик задач. kube-scheduler перебирает поды по приоритету (PriorityClass) — приоритетная очередь решает, кого размещать первым; при вытеснении (preemption) выбирается под с наименьшим приоритетом. cron-демоны и event-loop'ы держат задачи в куче по времени следующего запуска и за O(1) смотрят «ближайшую».
top-N самых медленных запросов. Чтобы найти 10 самых тяжёлых запросов в гигабайтном access-логе, не нужно сортировать весь файл — достаточно min-кучи размера 10 и одного прохода (O(n log K), память O(K)). Так же устроены topk-агрегации в системах мониторинга и SELECT ... ORDER BY ... LIMIT k в БД (top-K heap вместо полной сортировки).
Таймерные колёса и таймеры. Очередь таймеров (timer wheel / min-heap по дедлайну) в ядре ОС, в Nginx, в рантаймах Go и Node.js: на вершине — ближайшее по времени событие, поэтому проверка «не пора ли сработать» стоит O(1), а вставка/удаление таймера — O(log n).

Связь с другими лабами¶

Куча — это ещё один способ организовать «дерево в массиве»: в lab02 бинарное дерево поиска (BST) хранилось узлами со ссылками и держало полный порядок (левый < корень < правый), а здесь дерево закодировано индексами и поддерживает лишь частичный порядок (родитель vs потомки). BST отвечает на «найди элемент X», куча — на «дай экстремум». Heapsort из этой лабы дополняет сортировки из lab03: гарантированный O(n log n) без рекурсии и без деградации до O(n²), в отличие от quicksort.