➜
This issue tracker has been migrated to GitHub,
and is currently read-only.
For more information,
see the GitHub FAQs in the Python's Developer Guide.
Created on 2013-10-30 06:01 by Blaise.Gassend, last changed 2022-04-11 14:57 by admin. This issue is now closed.
| Messages (3) | |||
|---|---|---|---|
| msg201712 - (view) | Author: Blaise Gassend (Blaise.Gassend) | Date: 2013-10-30 06:01 | |
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 |
|||
| msg201717 - (view) | Author: Raymond Hettinger (rhettinger) *  |
Date: 2013-10-30 07:33 | |
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. |
|||
| msg201744 - (view) | Author: Blaise Gassend (Blaise.Gassend) | Date: 2013-10-30 16:25 | |
I stand corrected. Sorry for the noise. |
|||
| History | |||
|---|---|---|---|
| Date | User | Action | Args |
| 2022-04-11 14:57:52 | admin | set | github: 63644 |
| 2013-10-30 16:25:31 | Blaise.Gassend | set | messages: + msg201744 |
| 2013-10-30 07:33:02 | rhettinger | set | status: open -> closed resolution: not a bug messages: + msg201717 |
| 2013-10-30 07:17:48 | rhettinger | set | assignee: docs@python -> rhettinger nosy: + rhettinger |
| 2013-10-30 06:01:21 | Blaise.Gassend | create | |