What is the complexity of heap operations?

Operations with a binary heap (usually implemented) have the following complexity:

• Insert: O(log n). A new element is added to the end, and then a "heapify up" operation is performed to restore the heap properties. In the worst case, the bubble-up occurs up to the root, which is logarithmic in the height of the tree.

• Extract-Min/Max: O(log n). The root element (minimum/maximum) is removed, the last element is placed in its position, and then a "heapify down" operation is performed to restore the heap properties. In the worst case, the sift-down occurs to the leaf.

• Peek/Top: O(1). The minimum/maximum element is at the root of the heap and is directly accessible.

• BuildHeap from array: O(n). Although each heapifyDown call takes O(log n), the optimized heap construction algorithm, which applies heapifyDown to all non-leaf nodes from bottom to top, has linear complexity.

// Example pseudocode for Insert
void Insert(Heap& heap, int value) {
    heap.array.push_back(value);
    heapifyUp(heap.array, heap.array.size() - 1); // Restoring heap properties
}

// Example pseudocode for Extract-Min
int ExtractMin(Heap& heap) {
    if (heap.array.empty()) {
        // Error handling or empty heap
        return -1;
    }
    int minValue = heap.array[0];
    heap.array[0] = heap.array.back();
    heap.array.pop_back();
    heapifyDown(heap.array, 0); // Restoring heap properties
    return minValue;
}

// Example pseudocode for Peek/Top
int PeekMin(const Heap& heap) {
    if (heap.array.empty()) {
        // Error handling or empty heap
        return -1;
    }
    return heap.array[0];
}