Хороша тогда, когда нам нужно часто брать минимальный элемент.
Реализация
MinHeap with simple array
MinHeap with sorted array
MinHeap with (nearly completed) binary tree
Функции и их асимптотическая сложность
У heap есть 3 функции:
- min() - возвращает минимальный элемент кучи
- extractMin() - удаляет и возвращает минимальный элемент кучи
- insert(x) - вставляет элемент в кучу
И одно свойство:
- height - высота. Считается по количеству рёбер. Высота кучи - $\theta(\log(n))$.
| Technique |
min() |
extractMin() |
insert(x) |
| simple array |
O(n) |
O(n) |
O(1) |
| sorted array |
O(1) |
O(1) |
O(n) |
| binary tree |
O(1) |
O(logn) |
O(logn) |