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

Blaise Gassend added the comment: I stand corrected. Sorry for the noise. -- ___ Python tracker ___ ___ Python-bugs-list mailing list

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

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

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

Changes by Raymond Hettinger : -- assignee: docs@python -> rhettinger nosy: +rhettinger ___ Python tracker ___ ___ Python-bugs-list ma

[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 wors