the first heappop() is not the min of array, while it's the first index.
After that, heappop() works
I thought maybe it's the automatic heapify() after heappop()? check the documents but find nothing
>>> a = [412,23,24,24,32,5,324,12,41,125,5,32,41,24,12,5,34,1]
>>> heappop(a)
412
>>> heappop(a)
1
>>> heappop(a)
23
>>> a
[24, 24, 5, 12, 32, 32, 324, 5, 41, 125, 5, 34, 41, 24, 12]
BTW, if you heapify() a at first, the heappop() works well. Would be appreciated if any explanation on it. Thank you!
>>> a = [412,23,24,24,32,5,324,12,41,125,5,32,41,24,12,5,34,1]
>>> heapify(a)
>>> a
[1, 5, 5, 5, 32, 24, 12, 12, 24, 125, 412, 32, 41, 24, 324, 23, 34, 41]
>>> heappop(a)
1
>>> heappop(a)
5
>>> heappop(a)
5
>>> heappop(a)
5
>>> heappop(a)
12
The documentation says:
To create a heap, use a list initialized to
[], or you can transform a populated list into a heap via functionheapify().
As you have not done this in the first code block, your list is not a heap.
Functions like heappush, heappop, heappushpop, heapreplace maintain the heap invariant. But this implies that the list should be a heap before the call is made. Only then is it guaranteed that the list will still be a heap after the call.
These methods have a O(logn) time complexity, so they could not possibly make a heap from any random list. heapify has a time complexity of O(n). The power of a heap is that once you have established it, you can make use of the efficient methods to handle it, without having to call the more expensive heapify again.