heapq.heapify is n log(n), not linear

[BlaiseGassend]

BPO	19445
Nosy	@rhettinger

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = 'https://github.com/rhettinger'
closed_at = <Date 2013-10-30.07:33:02.870>
created_at = <Date 2013-10-30.06:01:21.201>
labels = ['invalid', 'docs']
title = 'heapq.heapify is n log(n), not linear'
updated_at = <Date 2013-10-30.16:25:31.383>
user = 'https://bugs.python.org/BlaiseGassend'

bugs.python.org fields:

activity = <Date 2013-10-30.16:25:31.383>
actor = 'Blaise.Gassend'
assignee = 'rhettinger'
closed = True
closed_date = <Date 2013-10-30.07:33:02.870>
closer = 'rhettinger'
components = ['Documentation']
creation = <Date 2013-10-30.06:01:21.201>
creator = 'Blaise.Gassend'
dependencies = []
files = []
hgrepos = []
issue_num = 19445
keywords = []
message_count = 3.0
messages = ['201712', '201717', '201744']
nosy_count = 3.0
nosy_names = ['rhettinger', 'docs@python', 'Blaise.Gassend']
pr_nums = []
priority = 'normal'
resolution = 'not a bug'
stage = None
status = 'closed'
superseder = None
type = None
url = 'https://bugs.python.org/issue19445'
versions = ['Python 2.6', 'Python 3.1', 'Python 2.7', 'Python 3.2', 'Python 3.3', 'Python 3.4', 'Python 3.5']

[BlaiseGassend]

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

[rhettinger]

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.

[BlaiseGassend]

I stand corrected. Sorry for the noise.