Что такое куча (heap) и как она реализует приоритетную очередь?

Question

Accepted Answer

**Бинарная куча** — это полное бинарное дерево, хранящееся в массиве, которое поддерживает **свойство кучи**: в **min-куче** каждый родитель ≤ его детей, поэтому **минимум всегда в корне**. Это делает её стандартной реализацией **приоритетной очереди**.

## Расположение в массиве

```text
       1               index: 0  1  2  3  4
      / \              array: [1, 3, 5, 8, 4]
     3   5             parent(i) = (i-1)//2
    / \                left(i)   = 2i+1
   8   4               right(i)  = 2i+2
```

## Операции

```python
import heapq
h = []
heapq.heappush(h, 5)   # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0]        # peek min -> O(1)
heapq.heappop(h)       # O(log n) — remove root, sift down -> 1
```

## Сложность

| Операция | Время |
|---|---|
| peek min/max | O(1) |
| push (вставка) | O(log n) |
| pop (извлечение) | O(log n) |
| build heap из n элементов | O(n) |

## Когда использовать

- **Планирование** по приоритету (например, планировщики задач ОС).
- **Dijkstra / Prim** алгоритмы поиска кратчайшего пути и MST.
- **Top-K** задачи и потоковые медианы.
- **Heap sort** (in-place O(n log n)).

## Почему это важно

Куча даёт вам следующий наиболее важный элемент мгновенно, не держа всё полностью отсортированным, что намного дешевле, чем переосортировка.

Она является основой приоритетных алгоритмов и частым инструментом в интервью для вопросов "k самых больших/маленьких".

Операция	Время
peek min/max	O(1)
push (вставка)	O(log n)
pop (извлечение)	O(log n)
build heap из n элементов	O(n)