Что такое бинарная куча?

Что такое бинарная куча?

Бинарная куча (Binary Heap) — это полное бинарное дерево, которое удовлетворяет свойству кучи. Это одна из наиболее эффективных структур данных для реализации приоритетной очереди и сортировки.

Основные свойства

Структурное свойство: Бинарная куча — это полное бинарное дерево, где все уровни заполнены полностью, кроме возможно последнего уровня, который заполняется слева направо.

Свойство кучи (Heap Property):

• Max-Heap: Каждый родитель больше или равен своим детям
• Min-Heap: Каждый родитель меньше или равен своим детям

Представление в массиве: Бинарная куча обычно хранится в массиве, где для элемента с индексом i:

• Левый ребёнок находится в позиции 2*i + 1
• Правый ребёнок находится в позиции 2*i + 2
• Родитель находится в позиции (i - 1) / 2

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

Insert (вставка) — O(log n):

void insert(int value) {
    heap.push_back(value);
    int index = heap.size() - 1;
    
    while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
        std::swap(heap[index], heap[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

Extract Max (извлечение максимума) — O(log n):

int extractMax() {
    int max = heap[0];
    heap[0] = heap.back();
    heap.pop_back();
    
    int index = 0;
    while (true) {
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        
        if (left < heap.size() && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < heap.size() && heap[right] > heap[largest]) {
            largest = right;
        }
        
        if (largest == index) break;
        std::swap(heap[index], heap[largest]);
        index = largest;
    }
    
    return max;
}

Peek (просмотр максимума) — O(1):

int getMax() {
    return heap[0];
}

Build Heap (построение кучи) — O(n):

void buildHeap(std::vector<int>& arr) {
    heap = arr;
    for (int i = heap.size() / 2 - 1; i >= 0; i--) {
        siftDown(i);
    }
}

Практическое применение

Приоритетная очередь:

std::priority_queue<int> pq;
pq.push(5);
pq.push(10);
pq.push(3);
std::cout << pq.top();
pq.pop();

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

Преимущества

• Очень эффективна для приоритетных очередей
• Хорошая локальность памяти (массив)
• Быстрое построение O(n)
• Простая реализация

Недостатки

• Нет быстрого поиска элемента
• Не подходит для упорядоченного обхода
• Сложнее балансировка, чем в AVL деревьях

Реальные применения в Backend

• Dijkstra Algorithm — поиск кратчайшего пути
• Prim Algorithm — минимальное остовное дерево
• Task Scheduler — управление задачами по приоритетам
• Load Balancing — распределение нагрузки
• Event Simulation — обработка событий в порядке времени