Showing content from http://mail.python.org/pipermail/python-dev/attachments/20161211/fa3f063e/attachment-0001.html below:
<div dir="ltr">Hello,<div><br></div><div>Current heapify documentation says it takes linear time</div><div><br></div><div>  <a href="https://docs.python.org/3/library/heapq.html#heapq.heapify">https://docs.python.org/3/library/heapq.html#heapq.heapify</a><br></div><div><br></div><div>However, investigating the code (Python 3.5.2) I saw this:</div><div><br></div><div><div><font face="monospace, monospace">  def heapify(x):</font></div><div><font face="monospace, monospace">    """Transform list into a heap, in-place, in O(len(x)) time."""</font></div><div><font face="monospace, monospace">    n = len(x)</font></div><div><font face="monospace, monospace">    # Transform bottom-up. The largest index there's any point to looking at</font></div><div><font face="monospace, monospace">    # is the largest with a child index in-range, so must have 2*i + 1 < n,</font></div><div><font face="monospace, monospace">    # or i < (n-1)/2. If n is even = 2*j, this is (2*j-1)/2 = j-1/2 so</font></div><div><font face="monospace, monospace">    # j-1 is the largest, which is n//2 - 1. If n is odd = 2*j+1, this is</font></div><div><font face="monospace, monospace">    # (2*j+1-1)/2 = j so j-1 is the largest, and that's again n//2-1.</font></div><div><font face="monospace, monospace">    for i in reversed(range(n//2)):</font></div><div><font face="monospace, monospace">      _siftup(x, i)</font></div></div><div><br></div><div>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.</div><div><br></div><div>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).</div><div><br></div><div>[]'s</div><div>Rafael</div></div>
RetroSearch is an open source project built by @garambo
| Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4