Какова сложность операций с кучей?

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

• Вставка элемента (Insert): O(log n). Новый элемент добавляется в конец, а затем выполняется операция "всплывания" (heapify up) для восстановления свойств кучи. В худшем случае всплывание происходит до корня, что логарифмично по высоте дерева.

• Удаление минимального/максимального элемента (Extract-Min/Max): O(log n). Корневой элемент (минимальный/максимальный) удаляется, последний элемент помещается на его место, а затем выполняется операция "просеивания вниз" (heapify down) для восстановления свойств кучи. В худшем случае просеивание происходит до листа.

• Просмотр минимального/максимального элемента (Peek/Top): O(1). Минимальный/максимальный элемент находится в корне кучи и доступен напрямую.

• Построение кучи из массива (BuildHeap): O(n). Несмотря на то, что каждый вызов heapifyDown занимает O(log n), оптимизированный алгоритм построения кучи, применяющий heapifyDown ко всем нелистовым узлам снизу вверх, имеет линейную сложность.

// Пример псевдокода для Insert
void Insert(Heap& heap, int value) {
    heap.array.push_back(value);
    heapifyUp(heap.array, heap.array.size() - 1); // Восстановление свойств кучи
}

// Пример псевдокода для Extract-Min
int ExtractMin(Heap& heap) {
    if (heap.array.empty()) {
        // Обработка ошибки или пустой кучи
        return -1;
    }
    int minValue = heap.array[0];
    heap.array[0] = heap.array.back();
    heap.array.pop_back();
    heapifyDown(heap.array, 0); // Восстановление свойств кучи
    return minValue;
}

// Пример псевдокода для Peek/Top
int PeekMin(const Heap& heap) {
    if (heap.array.empty()) {
        // Обработка ошибки или пустой кучи
        return -1;
    }
    return heap.array[0];
}