Бинарная куча — структура данных на основе почти полного бинарного дерева,
в котором выполняется свойство кучи.
Чаще всего бинарную кучу используют для реализации:
очереди с приоритетом
Главная идея:
лучший элемент всегда находится в корне
Для min-heap лучший элемент — минимальный.
Для max-heap лучший элемент — максимальный.
Термины
heap -> куча
binary heap -> бинарная куча
root -> корень
parent -> родитель
left child -> левый ребёнок
right child -> правый ребёнок
min-heap -> куча с минимумом в корне
max-heap -> куча с максимумом в корне
sift up -> поднять элемент вверх
sift down -> опустить элемент вниз
heapify -> построить кучу из массива
Бинарная куча задаётся тремя вещами:
1. почти полное бинарное дерево
2. свойство кучи
3. массивное представление дерева
Структура кучи
Структура отвечает на вопрос:
Как быстро получить минимальный или максимальный элемент?
Пример min-heap:
1
/ \
3 5
/ \ /
7 9 8
Минимальный элемент находится в корне:
root = 1
Та же куча в массиве:
heap = [1, 3, 5, 7, 9, 8]
Почти полное бинарное дерево
Бинарная куча хранится как почти полное бинарное дерево.
Это значит:
все уровни, кроме последнего, заполнены полностью
последний уровень заполняется слева направо
Пример корректной формы:
1
/ \
3 5
/ \ /
7 9 8
Пример некорректной формы для бинарной кучи:
1
/ \
3 5
/ \
8 9
Здесь на последнем уровне элементы не заполнены слева направо.
Свойство кучи
Min-Heap
В min-heap каждый родитель не больше своих детей:
parent <= child
Пример:
1
/ \
3 5
/ \ /
7 9 8
Для каждого ребра:
1 <= 3
1 <= 5
3 <= 7
3 <= 9
5 <= 8
Поэтому минимум находится в корне.
Max-Heap
В max-heap каждый родитель не меньше своих детей:
parent >= child
Пример:
9
/ \
7 8
/ \ /
1 3 5
Для каждого ребра:
9 >= 7
9 >= 8
7 >= 1
7 >= 3
8 >= 5
Поэтому максимум находится в корне.
Массивное представление
Бинарную кучу обычно хранят в массиве.
Для массива:
heap = [1, 3, 5, 7, 9, 8]
индексы:
index: 0 1 2 3 4 5
value: 1 3 5 7 9 8
Связи между индексами:
parent(i) = (i - 1) // 2
left(i) = 2 * i + 1
right(i) = 2 * i + 2
Пример:
i = 1
heap[i] = 3
parent(1) = 0 -> heap[0] = 1
left(1) = 3 -> heap[3] = 7
right(1) = 4 -> heap[4] = 9
Массив удобен потому, что не нужны явные ссылки на детей и родителей.
Базовые операции
Peek
Посмотреть корень:
peek(heap)
Для min-heap:
heap[0] -> минимальный элемент
Для max-heap:
heap[0] -> максимальный элемент
Сложность:
O(1)
Push
Добавить элемент в кучу:
push(heap, x)
Алгоритм:
1. добавить x в конец массива
2. поднять x вверх, пока свойство кучи нарушено
Подъём вверх называется:
sift up
Пример для min-heap:
heap = [1, 3, 5, 7, 9, 8]
push(2)
Сначала добавляем в конец:
[1, 3, 5, 7, 9, 8, 2]
2 меньше родителя 5, значит меняем их:
[1, 3, 2, 7, 9, 8, 5]
Теперь родитель 1 меньше 2, свойство кучи восстановлено.
Сложность:
O(log n)
Pop
Удалить и вернуть корень:
pop(heap)
Алгоритм:
1. сохранить корень как ответ
2. перенести последний элемент в корень
3. удалить последний элемент
4. опустить новый корень вниз, пока свойство кучи нарушено
Опускание вниз называется:
sift down
Пример для min-heap:
heap = [1, 3, 5, 7, 9, 8]
pop() -> 1
Переносим последний элемент в корень:
[8, 3, 5, 7, 9]
8 больше меньшего ребёнка 3, меняем:
[3, 8, 5, 7, 9]
8 больше меньшего ребёнка 7, меняем:
[3, 7, 5, 8, 9]
Свойство кучи восстановлено.
Сложность:
O(log n)
Heapify
Построить кучу из произвольного массива:
heapify(arr)
Пример:
arr = [7, 1, 5, 3, 9, 8]
heapify(arr)
После построения min-heap один из корректных вариантов:
[1, 3, 5, 7, 9, 8]
Сложность эффективного heapify:
O(n)
Это быстрее, чем добавлять n элементов по одному:
n * O(log n) = O(n log n)
Таблица сложностей
| Операция | Сложность |
|---|---|
peek() |
O(1) |
push(x) |
O(log n) |
pop() |
O(log n) |
heapify(arr) |
O(n) |
| поиск произвольного значения | O(n) |
| удаление произвольного значения | O(n) |
Почему высота равна O(log n)
Бинарная куча — почти полное бинарное дерево.
На каждом уровне количество возможных узлов удваивается:
1, 2, 4, 8, 16, ...
Поэтому при n элементах высота дерева:
O(log n)
Операции sift up и sift down проходят только один путь по высоте дерева,
поэтому стоят O(log n).
Бинарная куча и отсортированный массив
Куча не хранит элементы полностью отсортированными.
Для min-heap верно только локальное свойство:
родитель <= дети
Но между соседними элементами массива полного порядка может не быть:
heap = [1, 3, 5, 7, 9, 8]
Это корректная куча, хотя массив не обязан быть полностью отсортированным для
любой формы кучи.
Главное преимущество кучи:
можно быстро получить лучший элемент без полной сортировки
Бинарная куча и очередь с приоритетом
Очередь с приоритетом — абстракция:
push элемент с приоритетом
pop элемент с лучшим приоритетом
Бинарная куча — один из способов эффективно реализовать эту абстракцию:
peek -> O(1)
push -> O(log n)
pop -> O(log n)
То есть:
Priority Queue = что нужно уметь
Binary Heap = как это можно хранить
Python
В Python бинарная куча доступна через модуль:
heapq
heapq работает как min-heap.
Пример:
import heapq
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
print(heap[0]) # 1
print(heapq.heappop(heap)) # 1
print(heapq.heappop(heap)) # 3
print(heapq.heappop(heap)) # 5
Построение кучи из массива:
import heapq
arr = [7, 1, 5, 3, 9, 8]
heapq.heapify(arr)
print(arr)
print(arr[0]) # минимальный элемент
Для max-heap часто используют отрицательные значения:
import heapq
heap = []
heapq.heappush(heap, -5)
heapq.heappush(heap, -1)
heapq.heappush(heap, -9)
print(-heapq.heappop(heap)) # 9
print(-heapq.heappop(heap)) # 5
print(-heapq.heappop(heap)) # 1
Типичные применения
очередь с приоритетом
Dijkstra
A*
Prim
top K elements
merge K sorted lists
heap sort
медиана потока чисел
симуляции событий
Формальная схема
BinaryHeap = {
elements: heap[0..n-1],
shape: almost complete binary tree,
order: min-heap или max-heap,
root: heap[0],
size: n
}
Операции кучи изменяют или используют одну из четырёх сущностей:
корень
родитель
ребёнок
свойство кучи
Примеры:
push(x) -> добавляет элемент в конец и делает sift up
pop() -> удаляет корень и делает sift down
peek() -> читает корень
heapify -> восстанавливает свойство кучи для всего массива
Минимальная формулировка:
бинарная куча = почти полное бинарное дерево с быстрым доступом к минимуму или максимуму
