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

Blaise Gassend added the comment: I stand corrected. Sorry for the noise. -- ___ Python tracker <http://bugs.python.org/issue19445> ___ ___ Python-bugs-list mailin

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

New submission from Blaise Gassend: The documentation for heapq.heapify indicates that it runs in linear time. I believe that this is incorrect, and that it runs in worst case n * log(n) time. I checked the implementation, and there are indeed n _siftup operations, which each appear to be