Why heappop time complexity is O(logn) (not O(n)) in python?

Question

For a list, the heappop will pop out the front element. Remove an element from the front of a list has time complexity O(n). Do I miss anything?

Answer 1

A heappop() rearranges log(n) elements in the list so that it doesn't have to shift every element.

This is easy to see:

>>> from random import randrange
>>> from heapq import heapify, heappop
>>> h = [randrange(1000) for i in range(15)]
>>> heapify(h)
>>> h
[80, 126, 248, 336, 335, 413, 595, 405, 470, 592, 540, 566, 484, 970, 963]
>>> heappop(h)
80
>>> h
[126, 335, 248, 336, 540, 413, 595, 405, 470, 592, 963, 566, 484, 970]
>>> #       ^----^---------^----^----^----^----^---------^----^----^--- elements that didn't move

Note that the popping operation didn't move most of the elements (for example 248 is in the same position before and after the heappop).