> On Dec 12, 2016, at 8:12 AM, Raymond Hettinger
> wrote:
>
> The heapify() algorithm is well known and well studied. A quick Google
> search turns up plenty of explanations:
> https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=complexity%20of%20heapify
>
>
> al
> On Dec 11, 2016, at 1:38 PM, Rafael Almeida wrote:
>
> 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
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)
