> On Dec 11, 2016, at 1:38 PM, Rafael Almeida <almeida...@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).
Hello Rafael, 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 https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=complexity%20of%20heapify Data Structures Heap, Heap Sort & Priority Queue https://www.google.com/webhp?sourceid=chrome-instant&ion=1&espv=2&ie=UTF-8#q=complexity%20of%20heapify 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. Raymond Hettinger _______________________________________________ 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
