Binary Heap (Двоичная куча)

Что такое Binary Heap

Binary Heap — полное двоичное дерево, удовлетворяющее свойству кучи: каждый узел больше (или меньше) своих потомков. Это делает кучу идеальной структурой для реализации приоритетных очередей.

Предложена Дж. Уильямсом в 1964 году как основа алгоритма HeapSort.

Два вида кучи

Ключевые свойства

Хранение в массиве

Главная особенность: дерево хранится в обычном массиве, без указателей:

        1
       / \
      3   2
     / \ / \
    7  4 5  6

Массив: [ _, 1, 3, 2, 7, 4, 5, 6 ]  (индекс с 1)
            0  1  2  3  4  5  6  7

Навигация по индексам:

Для узла с индексом i:
┌─────────────────────────────────┐
│  Родитель   →  i / 2            │
│  Левый сын  →  2 * i            │
│  Правый сын →  2 * i + 1        │
└─────────────────────────────────┘

(при индексации с 0: parent = (i-1)/2, left = 2i+1, right = 2i+2)

Визуализация Max-Heap

Массив: [100, 85, 90, 70, 60, 75, 80, 40, 50, 55]
Индекс:   0    1   2   3   4   5   6   7   8   9

Основные операции

🔼 Sift Up (всплытие) — вспомогательная

Используется после вставки: новый элемент добавляется в конец и «всплывает» вверх.

Вставка 95 в Max-Heap:

[100, 85, 90, 70, 60, 75, 80, 40, 50, 55, 95]
                                           ↑ добавили в конец

95 > 60 (родитель) → меняем местами
95 > 85 (родитель) → меняем местами
95 < 100 (родитель) → стоп

Результат: [100, 95, 90, 70, 85, 75, 80, 40, 50, 55, 60]

def sift_up(heap, i):
    while i > 0:
        parent = (i - 1) // 2
        if heap[i] > heap[parent]:      # для Max-Heap
            heap[i], heap[parent] = heap[parent], heap[i]
            i = parent
        else:
            break

🔽 Sift Down (погружение) — вспомогательная

Используется после удаления корня: последний элемент ставится на место корня и «тонет» вниз.

Удаление корня 100:
  Ставим последний элемент (60) на место корня
  [60, 95, 90, 70, 85, 75, 80, 40, 50, 55]

  60 < max(95, 90) = 95 → меняем с левым
  [95, 60, 90, 70, 85, 75, 80, 40, 50, 55]

  60 < max(70, 85) = 85 → меняем с правым
  [95, 85, 90, 70, 60, 75, 80, 40, 50, 55]

  60 > нет детей → стоп  ✓

def sift_down(heap, i, n):
    while True:
        largest = i
        left, right = 2*i + 1, 2*i + 2
        if left < n and heap[left] > heap[largest]:
            largest = left
        if right < n and heap[right] > heap[largest]:
            largest = right
        if largest == i:
            break
        heap[i], heap[largest] = heap[largest], heap[i]
        i = largest

➕ Вставка — O(log n)

1. Добавить элемент в конец массива
2. Sift Up от добавленного элемента

def push(heap, val):
    heap.append(val)
    sift_up(heap, len(heap) - 1)

🏆 Получить максимум/минимум — O(1)

def peek(heap):
    return heap[0]    # просто смотрим корень

🗑️ Удаление корня (Extract Max/Min) — O(log n)

1. Запомнить корень (результат)
2. Поставить последний элемент на место корня
3. Уменьшить размер кучи на 1
4. Sift Down от корня

def pop(heap):
    heap[0], heap[-1] = heap[-1], heap[0]
    val = heap.pop()
    sift_down(heap, 0, len(heap))
    return val

🏗️ Построение кучи из массива — O(n)

Наивный способ (n вставок) = O(n log n)
Оптимальный способ (Флойд, 1964) = O(n) — sift_down от середины к корню:

def heapify(arr):
    n = len(arr)
    # Начинаем с последнего внутреннего узла
    for i in range(n // 2 - 1, -1, -1):
        sift_down(arr, i, n)

Почему O(n)? Большинство узлов — листья (n/2 штук), 
они делают 0 операций. Узлы выше делают O(1), O(2)...
Суммарно: O(n) по формуле геометрической прогрессии.

HeapSort — O(n log n)

Куча лежит в основе классического алгоритма сортировки:

1. Построить Max-Heap из массива     → O(n)
2. n раз: извлечь максимум           → O(n log n)
   - поменять корень с последним
   - уменьшить размер кучи
   - sift_down

Сортировка на месте, без доп. памяти!

def heap_sort(arr):
    n = len(arr)
    heapify(arr)                           # O(n)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]   # корень в конец
        sift_down(arr, 0, i)              # O(log n)

Сложность операций

{
  "title": { "text": "Сложность операций Binary Heap", "left": "center" },
  "tooltip": { "trigger": "axis" },
  "legend": { "data": ["O(1)", "O(log n)", "O(n)"], "bottom": 0 },
  "xAxis": {
    "type": "category",
    "data": ["1K", "10K", "100K", "1M", "10M"]
  },
  "yAxis": {
    "type": "value",
    "name": "Операций"
  },
  "series": [
    {
      "name": "O(1)",
      "type": "line",
      "data": [1, 1, 1, 1, 1],
      "smooth": true,
      "lineStyle": { "color": "#5cb85c", "width": 3 }
    },
    {
      "name": "O(log n)",
      "type": "line",
      "data": [10, 13, 17, 20, 23],
      "smooth": true,
      "lineStyle": { "color": "#f0ad4e", "width": 3 }
    },
    {
      "name": "O(n)",
      "type": "line",
      "data": [1000, 10000, 100000, 1000000, 10000000],
      "smooth": true,
      "lineStyle": { "color": "#d9534f", "width": 2, "type": "dashed" }
    }
  ]
}

Плюсы и минусы

Где используется

Итоговое сравнение всех четырёх структур