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 <rep...@bugs.python.org> <http://bugs.python.org/issue19445> _______________________________________ _______________________________________________ Python-bugs-list mailing list Unsubscribe: https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com
