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 worst case log(n).
One example of the documentation pages that are wrong. http://docs.python.org/3.4/library/heapq.html#heapq.heappush ---------- assignee: docs@python components: Documentation messages: 201712 nosy: Blaise.Gassend, docs@python priority: normal severity: normal status: open title: heapq.heapify is n log(n), not linear versions: Python 2.6, Python 2.7, Python 3.1, Python 3.2, Python 3.3, Python 3.4, Python 3.5 _______________________________________ 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
