Mediumheapq
Что такое heapq?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
heapq — min-heap на основе list. h[0] — минимум без удаления. Не отсортирован полностью, только heap-ordered.
import heapq
h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
heapq.heappush(h, 2)
heapq.heappop(h) # 1 (минимум)
# heapify — превратить list в heap in-place O(n)
nums = [3, 1, 4, 1, 5]
heapq.heapify(nums)
# Top-K без полной сортировки
heapq.nlargest(3, nums) # [5, 4, 3]
heapq.nsmallest(3, nums) # [1, 1, 3]
# Max-heap через negate (или кортеж -priority, item)
heapq.heappush(h, (-priority, item))- Применения: priority queue, top-K, Dijkstra, A*, merge sorted streams (
heapq.merge); queue.PriorityQueue— thread-safe wrapper вокруг heapq.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.