# Putting more thoughts on heap and heapify

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 `heapify`

, `heappop`

and `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.