CODEWITHSUNDEEP
data-structurestime-complexityheap
Ayoub Omari
Ayoub Omari

Reputation: 906

Time complexity of the Heap pop operation

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)) ?

Upvotes: 3

Views: 24774

Answers (1)

Ayoub Omari
Ayoub Omari

Reputation: 906

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.

enter image description here

Upvotes: 13

Related Questions