Since there are different variations for heap implementation, the complexity also varies in the different implementation. One of the key facts for the heap is the extract operation that will always take O(1) time to get the maximum or minimum from the heap. Since we have focused on binary heap implementation, we are going to see the analysis of binary heap operations:
|
Operation |
Complexity - average |
Complexity - Worst |
|
Search |
O(n) |
O(n) |
|
Insert |
O(1) |
O(log n) |
|
Delete |
O(log n) |
O(log n) |
|
Extract |
O(1) |
O(1) |
|
Space |
O(n) |
O(n) |
Since the heap is not fully sorted, the search operation will take more than a regular binary search tree.