Search code examples
algorithmconstraintspermutationmin-heap

Is this right? Minheap

enter image description here

Hello, I am wondering if these x's are in the right position for the min heap? Am I correct?

Solution

  • The top position is not a possibility because the 3 would be larger than its children (somewhere below would be a 1 or 2).

    The second level is possible because 2 and 3 could be sibling children of 1.

    To be on the third level, the 3 would need to have 2 for an immediate parent, and 1 for a grandparent with nothing else in between.

    The fourth level is not possible because there you would need three ancestors of 3 that are smaller than three.

    The list form is a direct conversion from the tree form. So, that is a match as well.

    You might want to prove this yourself empirically by trying to insert every permutation of 9! into minheap and observing where the 3 is found. Here is a Python script that does that:

    from heapq import heapify
from itertools import permutations

has_three = [False] * 9
for t in permutations('123456789'):
    s = list(t)
    heapify(s)
    i = s.index('3')
    has_three[i] = True
print(has_three)

    And the results are:

    [False, True, True, True, True, True, True, False, False]