problem with insert function

[emmacgodfrey]

Hi @mikeizbicki,

I am trying to finish up the homework for this week, and I have encountered a very frustrating bug.

When I run the test cases, the first error I get is the following:

=================================== FAILURES ===================================
______________________________ test__Heap_insert _______________________________

    @given(xs=ints)
>   def test__Heap_insert(xs):

tests/test_Heap.py:75: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

xs = [0, 0, 0, 0, 0, 0, ...]

    @given(xs=ints)
    def test__Heap_insert(xs):
        xs = list(xs)
        heap = Heap()
        for x in xs:
            heap.insert(x)
            assert x in heap.to_list('inorder')
>           assert heap.is_heap_satisfied()
E           assert False
E            +  where False = <bound method Heap.is_heap_satisfied of Heap([0, -1, 0, 0, -1, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0])>()
E            +    where <bound method Heap.is_heap_satisfied of Heap([0, -1, 0, 0, -1, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0])> = Heap([0, -1, 0, 0, -1, 0, 0, 0, -2, 0, 0, 0, 0, 0, 0, 0]).is_heap_satisfied

tests/test_Heap.py:81: AssertionError
---------------------------------- Hypothesis ----------------------------------
Falsifying example: test__Heap_insert(
    xs=[0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, -2],
)

Upon testing this error manually, I agree that the heap is not satisfied. More specifically, this is the tree that I obtain.

>>> heap=Heap([0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, -2])
>>> str(heap)
'(-2 - (-1 - (0 - (-1 - (0 - - ) - ) - (0 - - ) ) - (0 - (0 - - ) - (0 - - ) ) ) - (0 - (0 - (0 - - ) - (0 - - ) ) - (0 - (0 - - ) - (0 - - ) ) ) )'

Aside from this case, I keep trying to insert lists of different sizes and compositions and my function seems to work.

For instance,

>>> heap = Heap([1,0,2,3,-2,-4,10,0,0,-2])
>>> str(heap)
'(-4 - (-2 - (0 - (3 - - ) - (0 - - ) ) - (0 - (1 - - ) - ) ) - (-2 - (2 - - ) - (10 - - ) ) )'
>>> heap.is_heap_satisfied()
True

I am stuck.

This is my code for my insert function. Any suggestions would be appreciated.

 82     def insert(self, value):
 83         '''
 84         Inserts value into the heap.
 85 
 86         FIXME:
 87         Implement this function.
 88 
 89         HINT:
 90         The pseudo code is
 91         1. Find the next position in the tree using the binary representation of the total number of     nodes
 92             1. You will have to explicitly store the size of your heap in a variable (rather than co    mpute it) to maintain the O(log n) runtime
 93             1. See https://stackoverflow.com/questions/18241192/implement-heap-using-a-binary-tree f    or hints
 94         1. Add `value` into the next position
 95         1. Recursively swap value with its parent until the heap property is satisfied
 96 
 97         HINT:
 98         Create a @staticmethod helper function,
 99         following the same pattern used in the BST and AVLTree insert functions.
100         '''
101         if self.root:
102             num_nodes = Heap._count_nodes(self.root)
103             binrep = "{0:b}".format(num_nodes + 1)
104             lbinrep = [int(x) for x in str(binrep)]
105             Heap._insert(value, self.root, lbinrep[1:])
106             Heap._trickle_up(value, self.root, lbinrep[1:])
107         else:
108             self.root = Node(value)
109 
110     @staticmethod
111     def _insert(value, path, lbinrep):
112         if len(lbinrep) == 1:
113             if lbinrep[0] == 1:
114                 path.right = Node(value)
115             if lbinrep[0] == 0:
116                 path.left = Node(value)
117         else:
118             if lbinrep[0] == 1:
119                 Heap._insert(value, path.right, lbinrep[1:])
120             if lbinrep[0] == 0:
121                 Heap._insert(value, path.left, lbinrep[1:])
122 
123     @staticmethod
124     def _trickle_up(value, path, lbinrep):
125         if len(lbinrep) > 0:
126             if len(lbinrep) == 1:
127                 if lbinrep[0] == 1:
128                    if value < path.value:
129                        temp = copy.copy(path.right.value)
130                        path.right.value = path.value
131                        path.value = temp
132                 elif lbinrep[0] == 0:
133                     if value < path.value:
134                         temp = copy.copy(path.left.value)
135                         path.left.value = path.value
136                         path.value = temp
137             else:
138                 if lbinrep[0] == 1:
139                     Heap._trickle_up(value, path.right, lbinrep[1:])
140                 elif lbinrep[0] == 0:
141                     Heap._trickle_up(value, path.left, lbinrep[1:])
142 
143             Heap._trickle_up(value, path, lbinrep[:-1])

Thanks,

Emma

[mikeizbicki]

You have a good falsifying example with

xs=[0, 0, 0, 0, 0, 0, 0, 0, 0, -1, -1, 0, 0, 0, 0, -2],

The next step is to figure out exactly which one of these items is causing the bad behavior. Do this by using

xs=[0]
xs=[0, 0]
xs=[0,0,0]
...

until you find the particular insert that is problematic. Then you'll be able to debug that particular insert in isolation.

Or, if you're feeling really savvy, you don't have to do a linear search to find the problematic insert; you could do a binary search to save yourself a bit of time.

[emmacgodfrey]

Hi @mikeizbicki ,

Yes, sorry I should have included that in the initial issue. The bug occurs at the very end of the list insertion (i.e. trying to insert -2). I have tried to debug with various print statements, and I still can't figure it out.

>>> heap = Heap()
>>> heap.insert_list([0,0,0,0,0,0,0,0,0,-1,-1,0,0,0,0])
>>> str(heap)
'(-1 - (-1 - (0 - (0 - - ) - (0 - - ) ) - (0 - (0 - - ) - (0 - - ) ) ) - (0 - (0 - (0 - - ) - (0 - - ) ) - (0 - (0 - - ) - (0 - - ) ) ) )'
>>> heap.insert_list([-2])
>>> str(heap)
'(-2 - (-1 - (0 - (-1 - (0 - - ) - ) - (0 - - ) ) - (0 - (0 - - ) - (0 - - ) ) ) - (0 - (0 - (0 - - ) - (0 - - ) ) - (0 - (0 - - ) - (0 - - ) ) ) )'

Somehow the -1 is moving further down in the heap...any thoughts?

[emmacgodfrey]

Found one of the bugs that was causing this failed test case. Thanks!