Отсортированный список даёт минимум за O(1), но вставка стоит O(n). В неотсортированном вставка O(1), а минимум ищется за O(n). Куча (heap) — золотая середина: вставка и удаление минимума за O(log n), взгляд на минимум за O(1). На ней строятся очередь с приоритетом и пирамидальная сортировка.

Min-куча из семи элементов как дерево и как массив
Min-куча из семи элементов как дерево и как массив

Что такое куча

  • Min-куча: каждый узел меньше или равен своим детям, поэтому корень — минимум. В max-куче наоборот.
  • Это полное двоичное дерево: все уровни заполнены, кроме, возможно, последнего, который заполняется слева направо.
  • Куча не отсортирована полностью: сохраняется только отношение родитель-ребёнок, соседи между собой не упорядочены.

Полнота позволяет хранить дерево в массиве без указателей. Для индекса i с нуля: родитель (i - 1) // 2, дети 2i + 1 и 2i + 2.

python
heap = [1, 3, 2, 7, 4, 5, 6]

def is_min_heap(a):
    return all(a[(i - 1) // 2] <= a[i] for i in range(1, len(a)))

i = 1
print("node", heap[i], "parent", heap[(i - 1) // 2])
print("children", heap[2 * i + 1], heap[2 * i + 2])
print(is_min_heap(heap), is_min_heap([3, 1, 2]))
text
node 3 parent 1
children 7 4
True False

push и pop

push добавляет элемент в конец и поднимает его: пока он меньше родителя, меняет их местами. pop забирает корень, ставит на его место последний элемент и опускает его: меняет с меньшим из детей, пока порядок не восстановится. Оба идут по одной ветке, значит, стоят O(log n).

pop: последний элемент встаёт в корень и опускается, меняясь с меньшим ребёнком
pop: последний элемент встаёт в корень и опускается, меняясь с меньшим ребёнком