Message201712
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 worst case log(n).
One example of the documentation pages that are wrong.
http://docs.python.org/3.4/library/heapq.html#heapq.heappush |
|
Date |
User |
Action |
Args |
2013-10-30 06:01:21 | Blaise.Gassend | set | recipients:
+ Blaise.Gassend, docs@python |
2013-10-30 06:01:21 | Blaise.Gassend | set | messageid: <1383112881.24.0.0958145237124.issue19445@psf.upfronthosting.co.za> |
2013-10-30 06:01:21 | Blaise.Gassend | link | issue19445 messages |
2013-10-30 06:01:20 | Blaise.Gassend | create | |
|