[Python-Dev] On time complexity of heapq.heapify (original) (raw)

Raymond Hettinger 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).

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

More information about the Python-Dev mailing list