Алгоритмы с нуля
Heap: priority queue и слияние k потоков
Читать про heap — не то же самое, что иметь тот, которому доверяешь. Постройте binary heap сами, оберните как priority queue, затем заставьте его отработать на двух флагманских задачах — top-k и k-way merge — на реалистичной работе: слиянии k отсортированных по времени потоков логов и выявлении самых медленных запросов. Доказывайте каждое утверждение O(…) замерами, а не верой.
Превратите модель юнита в работающий протестированный код: корректный heap на массиве с sift-up/sift-down и build-heap за O(n), обёртку priority queue и два приложения (top-k, k-way merge), чьи замеренные времена совпадают с предсказанием O(n log k).
Реализуйте binary heap и priority queue с нуля (без библиотечного heap), затем используйте их, чтобы (a) слить k отсортированных по времени потоков логов в один упорядоченный поток и (b) выдать top-k самых медленных запросов — проверяя, что замеренная стоимость каждой операции совпадает с её асимптотической границей.
- Все тесты корректности проходят: тест «извлечь всё» даёт отсортированный вывод для N = 100000; top-k возвращает ровно k наибольших с корнем, равным k-му по величине; вывод k-way merge глобально отсортирован и содержит каждый входной элемент ровно один раз.
- Таблица времён для build-heap (n = 10^4/10^5/10^6), показывающая почти линейный рост, рядом с временами вставки по одному, показывающими более крутую кривую n log n — замеренные, не оценочные.
- Таблица времён для k-way merge при фиксированном n с k = 2/8/32/128, показывающая тренд log k, рядом с временами наивного O(nk) слияния на идентичном входе.
- Абзац с разбором, который называет для каждого требования, какую ориентацию heap (min или max) и какой размер (k или n) вы выбрали и почему — привязывая каждое к инварианту вытеснения/продвижения.
- Добавьте индексированный binary heap (отслеживайте текущую позицию каждого элемента в массиве через map) с поддержкой decrease-key за O(log n) и используйте его для реализации кратчайших путей Dijkstra на небольшом взвешенном графе — показывая, почему обычный heap не смог бы сделать это эффективно.
- Добавьте потоковый top-k, который обрабатывает неограниченный генератор, ни разу не материализуя весь вход, и продемонстрируйте на потоке намного больше памяти, используя O(k) памяти.
- Реализуйте heap-sort на месте (постройте max-heap, затем повторно меняйте корень с концом и делайте sift-down) и сравните его время и число сравнений со встроенной сортировкой языка на тех же массивах.
- Добавьте вариант smallest-range поверх k-way merge: при слиянии k массивов отслеживайте наименьшее окно [min, max], содержащее хотя бы один элемент из каждого массива.
Это цикл, которого требует реальная задача на heap: постройте структуру корректно (sift-up/sift-down, heapify за O(n)), выставьте её за контрактом priority queue, затем выбирайте правильную ориентацию и размер под задачу — MIN-heap размера k, вытесняющий корень для top-k, min-heap на поток, продвигающийся по индексу для k-way merge. Что делает это уровнем сеньора — дисциплина проверки: вы замерили линейность build-heap, тренд log k у merge и инвариант heap-sort, вместо того чтобы доверять big-O на бумаге. Сделайте это раз здесь — и продакшен-версия станет мышечной памятью.