I’ve been trying to wrap my head around heaps recently. I’m specifically looking at heapq in Python and feel like the time complexity promises are a lie.

We’re promised the following time complexities (right?):

• heapify: O(n)
• push: O(log n)
• pop: O(log n)

But since heapq just operates on Python lists we are subject to the time complexities of normal list operations, and adding an element to a list or popping an element from a list can be O(n) since if we add or remove an element at the first position we need to shift all the other elements.

For heapq.heappush, I get that we can find the location where the element should be inserted in O(log n), but I don’t see how we can get around the O(n) list insert time.

Take the example of pq = [2, 3, 4, 5]. If we do heapq.heappush(pq, 1) we should end up with something like pq = [1, 2, 3, 4, 5]. The steps would be:

1. Find the index where the new element needs to be inserted (0): O(log n)
2. Shift all the elements in pq up one and insert 1 at index 0: O(n)

Time complexity: O(log n + n) ~ O(n)

What am I missing?