Hello,
Current heapify documentation says it takes linear time
https://docs.python.org/3/library/heapq.html#heapq.heapify
However, investigating the code (Python 3.5.2) I saw this:
def heapify(x):
"""Transform list into a heap, in-place, in O(len(x)) time."""
n = len(x)
# Transform bottom-up. The largest index there's any point to
looking at
# is the largest with a child index in-range, so must have 2*i + 1
< n,
# or i < (n-1)/2. If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so
# j-1 is the largest, which is n//2 - 1. If n is odd = 2*j+1, this
is
# (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.
for i in reversed(range(n//2)):
_siftup(x, i)
>From what I gather, _siftup(heap, pos) does not run in constant time, but
rather it runs in time proportional to the height of the subtree with root
in ``pos''. Although, according to the in-code comments, it should be
faster than creating a heap by calling heappush multiple times, I believe
the time complexity remains the same.
Although I had a hard time finding out the exact time complexity for that
particular function, I think it is closer to O(log(n!)) than to O(n). I
would be very happy to see an explanation as to why the time is O(n) (it
does not seem possible to me to create a heap of n numbers in such
runtime). However, if no one has a convincing argument, I'd rather omit
time complexity information from documentation (given that this analysis is
not made for the other functions either).
[]'s
Rafael
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
https://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
https://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
