[issue19445] heapq.heapify is n log(n), not linear
Raymond Hettinger
report at bugs.python.org
Wed Oct 30 08:33:02 CET 2013
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>
_______________________________________
More information about the Python-bugs-list
mailing list