[Python-Dev] On time complexity of heapq.heapify
raymond.hettinger at gmail.com
Mon Dec 12 11:12:08 EST 2016
> On Dec 11, 2016, at 1:38 PM, Rafael Almeida <almeidaraf at gmail.com> 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 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).
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
algorithm - How can building a heap be O(n) time complexity? - StackOverflow
Data Structures Heap, Heap Sort & Priority Queue
Sub tree rooted at i is a max heap. Simple bound:
– O(n) calls to MAX-HEAPIFY,
– Each of which takes O(lg n), – Complexity: O(n lg n).
– Thus, the running time of BUILD-MAX-HEAP is O(n).
Here's a more detailed explanation: http://www.cs.umd.edu/~meesh/351/mount/lectures/lect14-heapsort-analysis-part.pdf
If you have other follow-ups, please take this discussion to another list. This list is for the development of the Python core and not for general questions about algorithms or use of the language.
More information about the Python-Dev