Time complexity of the Heap pop operation

Question

For a long time, I have been assuming that the time complexity of the pop operation on a Heap is O(1).

Is it O(1) or O(log(n)) ?

Answer 1

Ok O(1) is only for retrieving the root of the heap. To delete this root, all heap implementations have a O(log(n)) time complexity. For example the python heapq module implements a heap with an array, and all the time the first element of the array is the root of the heap. So when deleting the root, there is a replacement process from the root down to the bottom of the heap that takes O(log(n)) time, O(log(n)) is the overall number of replacements.