[New-bugs-announce] [issue19445] heapq.heapify is n log(n), not linear

Blaise Gassend report at bugs.python.org
Wed Oct 30 07:01:21 CET 2013

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.

assignee: docs at python
components: Documentation
messages: 201712
nosy: Blaise.Gassend, docs at 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 <report at bugs.python.org>

More information about the New-bugs-announce mailing list