Вы знакомы с контейнером, таким как куча?

Да, знаком. Куча (heap) — это специализированное дерево, удовлетворяющее правилу кучи: для любой вершины ее значение должно быть не меньше (или не больше) значения любого из ее потомков.

Различают:

• Куча максимума (Max-heap): Значение родительской вершины всегда больше или равно значениям ее потомков. Максимальный элемент находится в корне.
• Куча минимума (Min-heap): Значение родительской вершины всегда меньше или равно значениям ее потомков. Минимальный элемент находится в корне.

Распространенная реализация кучи — бинарная куча, которая обычно представляется в виде массива. Связь родитель-потомок определяется индексами массива:

• Левый потомок элемента с индексом i находится по индексу 2*i + 1.
• Правый потомок элемента с индексом i находится по индексу 2*i + 2.
• Родитель элемента с индексом i находится по индексу (i - 1) / 2.

Основные операции и их временная сложность (для бинарной кучи):

Применение кучи:

• Реализация очередей с приоритетом.
• Алгоритм сортировки пирамидальная сортировка (Heap Sort).
• Алгоритмы построения графов (например, алгоритм Дейкстры, алгоритм Прима).

В C++ стандартная библиотека предоставляет std::priority_queue, который является адаптером контейнера и по умолчанию использует std::vector как базовый контейнер и реализует кучу максимума.

#include <queue>
#include <vector>
#include <iostream>

int main() {
    // Создание очереди с приоритетом (по умолчанию куча максимума)
    std::priority_queue<int> max_heap;

    // Добавление элементов
    max_heap.push(10);
    max_heap.push(30);
    max_heap.push(20);
    max_heap.push(5);

    // Извлечение элементов (в порядке убывания)
    while (!max_heap.empty()) {
        std::cout << max_heap.top() << " "; // Просмотр верхушки
        max_heap.pop(); // Удаление верхушки
    }
    std::cout << std::endl;

    // Создание кучи минимума
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    min_heap.push(10);
    min_heap.push(30);
    min_heap.push(20);
    min_heap.push(5);

    // Извлечение элементов (в порядке возрастания)
    while (!min_heap.empty()) {
        std::cout << min_heap.top() << " ";
        min_heap.pop();
    }
    std::cout << std::endl;

    return 0;
}