In a recent conversation, I was asked what the time complexity of
heapify is. I said O(N * Log N) confidently. After putting more thoughts on it, I found it’s not.
I read through the source code of Python3’s builtin lib
heapq, which provides a handful of methods such as
heappush. I found there is a bit more complicated math behind it, and a trade-off that the author made in the implementation.
Just be clear, in this article, heap is binary min-heap.