Mediumheap
Что такое heap (куча) и priority queue?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
Heap — complete binary tree, где parent имеет приоритет над children (min-heap: parent ≤ children). Реализация через array: для index i → parent = (i-1)//2, left = 2i+1, right = 2i+2.
import heapq
h = []
heapq.heappush(h, 3)
heapq.heappush(h, 1)
print(heapq.heappop(h)) # 1 (min)
heapq.heapify([3, 1, 2]) # O(n) in-place
heapq.nsmallest(2, h) # без полной сортировкиОперации: insert (sift up) O(log n), extract-min (sift down) O(log n), peek O(1), build heap O(n). Применения: Dijkstra/A*, merge K sorted lists, top-K, median of stream (два heap-а), Huffman coding. Heap sort — build O(n) + n extract → O(n log n). В Python heapq — min-heap, для max — negative keys. C++ std::priority_queue — max-heap по default.
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.