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

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

Существует два типа бинарных куч: максимальная куча и минимальная куча.

• Максимальная куча: Каждый родительский узел больше или равен своим дочерним узлам. Это означает, что самый большой элемент всегда находится в корне дерева.
• Минимальная куча: Каждый родительский узел меньше или равен своим дочерним узлам. Это означает, что самый маленький элемент всегда находится в корне дерева.

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

Пример кода: Реализация максимальной кучи

#include <iostream>
#include <vector>
​
class MaxHeap {
    std::vector<int> heap;
​
    // Вспомогательная функция для поддержания свойства кучи
    void heapifyUp(int index) {
        if (index && heap[parent(index)] < heap[index]) {
            std::swap(heap[index], heap[parent(index)]);
            heapifyUp(parent(index));
        }
    }
​
    // Вспомогательная функция для поддержания свойства кучи
    void heapifyDown(int index) {
        int left = leftChild(index);
        int right = rightChild(index);
        int largest = index;
​
        if (left < size() && heap[left] > heap[largest])
            largest = left;
​
        if (right < size() && heap[right] > heap[largest])
            largest = right;
​
        if (largest != index) {
            std::swap(heap[index], heap[largest]);
            heapifyDown(largest);
        }
    }
​
    // Возвращает индекс родительского узла
    int parent(int index) { return (index - 1) / 2; }
​
    // Возвращает индекс левого дочернего узла
    int leftChild(int index) { return 2 * index + 1; }
​
    // Возвращает индекс правого дочернего узла
    int rightChild(int index) { return 2 * index + 2; }
​
public:
    // Возвращает размер кучи
    int size() { return heap.size(); }
​
    // Проверяет, пуста ли куча
    bool empty() { return size() == 0; }
​
    // Добавляет элемент в кучу
    void insert(int element) {
        heap.push_back(element);
        heapifyUp(size() - 1);
    }
​
    // Удаляет и возвращает максимальный элемент (корень)
    int extractMax() {
        if (empty()) throw std::out_of_range("Heap is empty");
​
        int root = heap.front();
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
​
        return root;
    }
};
​
int main() {
    MaxHeap h;
    h.insert(3);
    h.insert(1);
    h.insert(6);
    h.insert(5);
    h.insert(9);
    h.insert(8);
​
    std::cout << "Max element: " << h.extractMax() << std::endl; // Выводит 9
    return 0;
}

Объяснение кода

• Класс MaxHeap: Реализует максимальную кучу с помощью вектора heap, который хранит элементы кучи.
• Методы heapifyUp и heapifyDown: Поддерживают свойство кучи после добавления или удаления элементов. heapifyUp используется при добавлении нового элемента, чтобы переместить его на правильное место, а heapifyDown — при удалении корня, чтобы восстановить свойство кучи.
• Методы parent, leftChild, rightChild: Возвращают индексы родительского, левого и правого дочернего узлов соответственно.
• Метод insert: Добавляет новый элемент в конец вектора и вызывает heapifyUp для поддержания свойства кучи.
• Метод extractMax: Удаляет и возвращает максимальный элемент (корень) кучи. После удаления корня последний элемент перемещается на его место, и вызывается heapifyDown для восстановления свойства кучи.
• Функция main: Демонстрирует использование кучи, добавляя элементы и извлекая максимальный элемент.