Is python's heapq.heapify() faster on a list that is close to a heap?

Question

Like the title says, I would like to know if python's heapq.heapify() will work faster on a list that is close to a heap or does it do the entire operation element by element on every list?

I'm debating on how often to use heapify().

Answer 1

The obvious answer is yes. If you supply a sorted array to heapify it won't have to perform any swaps at all. If you supply a reverse-sorted array it will have to perform the maximum number of swaps.

That said, there is no benefit to pre-sorting the array before passing it to heapify because the total time (i.e. analyzing and arranging the array, plus heapify time) will exceed the maximum time required for heapify to do its work on even the worst-case arrangement.

That said, you shouldn't have to call heapify more than once. That is, you call heapify to construct the heap. Then you call the heappush and heappop methods to add and remove items.

I suppose, if you have to add a large number of items to an existing heap, you could append them to an existing heap and then call heapify to re-build the heap. Hard to say the exact circumstances under which that would be useful. I'd certainly give any such code a big ol' WTF if I were to see it in a code review.