[issue19445] heapq.heapify is n log(n), not linear

[Raymond Hettinger]

Raymond Hettinger added the comment:

The run time is O(n) because the heapify algorithm runs bottom-to-top so most of the n//2 sift operations are working on very short heaps (i.e. half of them are at depth 1, a quarter of them are at depth 2, one eight at depth 3, etc).  Please take a look at on-line references for heapifying.

----------
resolution:  -> invalid
status: open -> closed

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue19445>
_______________________________________