0

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?

Improve this question
3
  • 2
    Both your expected and actual results respect the heap invariant: each element is less than either of its children. That is absolutely all you can expect from a heap, there is no one correct ordering of elements (other than the least element being at the root). Commented Dec 3, 2019 at 2:59
  • Thanks a lot @MarkMeyer I want to do a follow up and really appreciate your advice: suppose we run heapify on list [12,3,-2,6] (part of the list in my original question), I agree with you the order will be: [12], [3, 12], [-2, 12, 3], and if we add 6, it will be the left child of 12, but in order to maintain heap structure, we need to swap 12 and 6 to make sure the parent smaller than the child, so the result should [-2,6,3,12], but when I ran heapify for [12,3,-2,6] using my Jupiter notebook, I got [-2, 3, 12, 6], could you please let me know why I was wrong? Commented Dec 5, 2019 at 2:18
  • @M00000001 I was incorrect about the order of pushing items. Your order is how I would do it. Without looking at the internals I don't think you can know why Python chooses one over the other. Maybe is starts at the other end of the list. Heapifying [6, -2, 3, 12] gives me [-2, 6, 3, 12] Commented Dec 5, 2019 at 2:32

2 Answers 2

Reset to default
1

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].

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

I think it's named _siftup is because (at CS lectures), the parent node is also called the root node, so when the function is wrote up, the tree is upside down for them

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.