I ran the following piece of code
from heapq import heappop,heappush,heapify
nums = [12,3,-2,6,4,8,9]
heapify(nums)
print(nums)
And got the following results: [-2, 3, 8, 6, 4, 12, 9] But I expect the following results: [-2,4,3,12,6,8,9] since I expect we are pushing each item fropm nums (starting from 12, and one by one) into an empty list while maintaining heap data structure. Could anyone give me some guidance why I am wrong?
Let's draw a picture of your initial array: [12,3,-2,6,4,8,9]
12
/ \
3 -2
/ \ / \
6 4 8 9
The heapify function does not build a heap by repeated insertion. It uses Floyd's algorithm to rearrange an array into heap order in O(n) time. Search for "heapify" in https://github.com/python/cpython/blob/master/Lib/heapq.py. The relevant code is:
for i in reversed(range(n//2)):
_siftup(x, i)
(For some unknown reason, the author of heapq decided to call the operation that moves a node towards the leaf level "_siftup," which is terribly confusing. Most people call this operation "_siftdown." If you examine the code, though, the node is definitely moving towards the leaf level.)
In any case, there are 7 nodes in the heap. The first node this will affect is at index 3 in the array: the node with value 6. There's nothing to do at that node, because the node is already at the leaf level. It then tries to move node at index 2 (value -2), but it doesn't sift down at all. And the node with value 3 doesn't sift, either. So we're left with the root node, 12.
12 is larger than both children, so it's swapped with the smallest, giving:
-2
/ \
3 12
/ \ / \
6 4 8 9
And it's larger than both of those children, so it's swapped again with the smallest:
-2
/ \
3 8
/ \ / \
6 4 12 9
The array representation, then, is [-2, 3, 8, 6, 4, 12, 9].