[docs] [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 docs mailing list