-3

I'm learning the Heap data structure and found this link

I'm expecting the output of heapq.heapify([5, 7, 9, 1, 3]) to be

[1, 3, 9, 5, 7]

However, I saw it returns this:

[1, 3, 9, 7, 5]

As some suggested that the order on the same level does not matter, then I guess I just feel confused that how does the [5,7] in the original sequence swapped position since the order in the same level does not matter.

Could someone explain why it is like this?

Franva
  • 6,565
  • 23
  • 79
  • 144
  • 2
    Why do you think the returned ordering isn’t a valid heap? Do you understand the arrangement of nodes it corresponds to? – Sneftel Aug 13 '22 at 06:49
  • According to the definition, both the fourth and fifth elements are the child nodes of the second element and should be greater than the value of it. Is there anything wrong? – Mechanic Pig Aug 13 '22 at 07:00
  • @Sneftel you are making a false assumption. I am seeking for explanations to help me understand the returned result, not a complaint(accusing the result from that page is not valid). If you think you know the arrangement of nodes, you are more than welcome to explain it here and help others who have the same question. – Franva Aug 13 '22 at 07:01
  • @MechanicPig, for the 2 nodes on the same level, do they need to be in order as well? – Franva Aug 13 '22 at 07:04
  • @Franva No, they just need to be larger than their parent node. – Mechanic Pig Aug 13 '22 at 07:06
  • 1
    Fine, but then why did you expect that particular result? What about the result you got was inconsistent with your understanding of what the function is meant to do? – Sneftel Aug 13 '22 at 07:08
  • @MechanicPig thanks. I guess I just feel confused that how does the `[5,7]` in the original sequence swapped position since the order in the same level does not matter. – Franva Aug 13 '22 at 07:15
  • heapify explanation: https://youtu.be/HqPJF2L5h9U?t=2620 – Vladimir Fokow Aug 13 '22 at 07:18
  • @Sneftel omg, please do not point finger, this is not a blame, I simply just want to ask a question and got my confusion cleared. why so much hustle.... – Franva Aug 13 '22 at 07:19
  • 1
    @Franva I think you might be misinterpreting. The point of asking follow-up questions is not to “point fingers” but to identify what aspects of a complicated system have confused you. If you had answered them, rather than getting defensive, it would have helped people help you. – Sneftel Aug 13 '22 at 07:42
  • "As some suggested that the order on the same level does not matter" It doesn't, and therefore the behaviour isn't defined in the documentation. If you want to understand why the implementation has some specific but irrelevant behaviour, **read and debug the implementation**. – Karl Knechtel Aug 13 '22 at 07:51
  • @KarlKnechtel yep, before posting this question, I was trying to debug the code found in that link and it turns out the code uses heappush() which hides the implementation, hence this question was asked. – Franva Aug 13 '22 at 08:00

2 Answers2

3
57913    # Starting list

Following the "heapify" procedure (for the min-heap):

As explained in this video, we iterate through the elements of our list one by one from the right, and each iteration check if the heap below it is a valid heap. If not - we swap the elements of this sub-heap until it becomes valid.

       5
    7    9
  1   3

3: has no elements below it --> it's a valid heap

1: has no elements below it --> it's a valid heap

9: has no elements below it --> it's a valid heap

7 > min(1, 3),

1 < 3 --> so choose 1 to swap with 7

       5
    1    9
  7   3

5 > min(1, 9),

1 < 9 --> so choose 1 to swap with 5:

       1
    5    9
  7   3

5 > min(3, 7),

3 < 7 --> so choose 3 to swap with 5

       1
    3    9
  7   5

13975    # Result
Vladimir Fokow
  • 3,728
  • 2
  • 5
  • 27
  • Many thanks @Vladimir, showing the procedure of how to construct a heap is very helpful to assist understanding how this job got done :) from what you show above, may I assume that 1, the procedure starts from the bottom left leave node? then the 2nd leave node in the bottom level, then the next leave node in the bottom level until all bottom nodes are handled, 2. then travel up the the 2nd bottom level from the very left node til the very right node and repeat this procedure until the root of the tree? – Franva Aug 13 '22 at 07:38
  • 1
    @Franva, added some explanation that I found in the linked video – Vladimir Fokow Aug 13 '22 at 07:45
  • Nice, the way how you explain the procedure of heapify is very clear. Many thank :) – Franva Aug 13 '22 at 07:59
2

Note that the Heap data structure only guarantees the top to be the minimum [or maximum]. It isn't anything like a Binary Search Tree, which I gather is what you're expecting with the order.

The invariant for a Binary Search Tree is that that for every node x, all the keys in the left subtree should be smaller than x and all the keys in the right subtree should be greater than x.

However, in a Heap, the invariant is just that that every node x should be greater [or smaller] than its children. Note how it doesn't specify anything about its left or right subtree.

The sequence [1, 3, 9, 7, 5] is a valid heap. Note how every parent is smaller than its children.

       1
    3    9
  7   5
Preet Mishra
  • 389
  • 3
  • 7
  • thanks Preet, yep, I think I mixed it up with Binary Search Tree. However, since the order does not matter in a same level, then why the original `[5,7]` got swapped after the `heapify()`? – Franva Aug 13 '22 at 07:17
  • 1
    It is due to the `heapify()` implementation. Since the order doesn't matter for the invariant to hold, the elements could get swapped at times. Please refer to these answers for more context: https://stackoverflow.com/questions/9755721/how-can-building-a-heap-be-on-time-complexity, https://stackoverflow.com/questions/34329942/siftup-and-siftdown-operation-in-heap-for-heapifying-an-array#:~:text=siftDown%20swaps%20a%20node%20that,than%20the%20node%20above%20it.. – Preet Mishra Aug 13 '22 at 07:22