insert to max binary heap and ValueError

Question

I'm trying to write an insert function. But I'm so lost. I've got an the error:

ValueError: None is not in list for no reason.

My code:

def __init__(self):
    self.heap=[]
    self.size = 0
def parent(self,index):


    if index<=1:
        return None
    elif index>=self.size:
        return None
    else:
        return self.heap[int((index-1)/2)]

def swap(self, index1, index2):
    self.heap[index1-1], self.heap[index2-1] = self.heap[index2-1], self.heap[index1-1]

def insert(self,x):

    self.heap.append(x)
    self.size = self.size + 1
    #while currentsize :
        #if currentsize[x] > self.parent(self,x):
            #self.swap(currentsize[x],currentsize[int((x-1)/2)])
        #if x > self.parent(x):
            #self.swap((currentsize.index[x])+1, currentsize.index[self.parent(x)]+1)

    while self.heap.index(x)//2>0:
        if self.heap.index(x)>self.heap.index(self.parent(x)):
            #temp = a(x)
            #a.index(x//2) = a.index(x)
            #a.index(x) = temp
            self.swap(self.heap.index(x),self.heap.index(self.parent(x)))

This looks like a method, not a function. Can you add the code, that shows how you initialise `self.heap` and `self.parent`. You should also add the complete traceback and a sequence of arguments `x` that reproduces the error. — Eli Korvigo, Mar 23 '19 at 22:19
Missing context around heap function. Fixed your indentation and removed double script code (awaiting peer-review). — ZF007, Mar 23 '19 at 22:55
You haven't provided the traceback for the error. I suspect, the `None` comes from one of the `self.parent` calls, but I need a traceback to be sure. — Eli Korvigo, Mar 24 '19 at 11:04
As you can see I've updated my answer for you. There are inline comments explaining some things (a.k.a. local debugging using print statements). — ZF007, Mar 24 '19 at 23:18

ZF007 · Answer 1 · 2019-03-24T23:12:40.153

You have created self.size but forgot to give it variables from outside the defs. I've mainly focus on getting your code working for parent() and did some script clenching. I didn't check swap or insert defs but you'll get the hang of it now.

See another example how to use self here at another SO answer to a question. Lots of docs to find elsewhere.

The below code prints:

lol [12, 13] 0    # <--- string, list, value
t1
(None, 1)

Script:

def __init__(self, heap, size):
    self.heap = heap
    self.size = size
    print (type(self.size))

    print (self.size)

def parent(self, index):

    print ('lol', self, index)

    if index <= 1:
        print ('t1')
        return (None, 1)
    elif index >= x:
        print ('t2')
        return (None, 2)
    else:
        return self.heap[int((index - 1)/2)]

def swap(self, index_1, index_2):                   # Using underscore gives distinction between variable name (includes stringbased values) and real values. 
    self.heap[index_1 - 1], self.heap[index_2 - 1] = self.heap[index_2 - 1], self.heap[index_1 - 1]

def insert(self, x):

    self.heap.append(x)
    self.size = self.size + 1
    #while currentsize :
        #if currentsize[x] > self.parent(self,x):
            #self.swap(currentsize[x],currentsize[int((x-1)/2)])
        #if x > self.parent(x):
            #self.swap((currentsize.index[x])+1, currentsize.index[self.parent(x)]+1)

    hi =  self.heap.index(x)                        # < Reusable variable gives better readability of your script.

    while hi//2 > 0:

        hip = self.heap.index(self.parent(x))       # < Reusable variable gives better readability of your script.

        if hi > hip:
            #temp = a(x)
            #a.index(x//2) = a.index(x)
            #a.index(x) = temp
            self.swap(hi, hip)

if __name__ == "__main__":

    x = 12
    y = 13
    h = [x, y]    # <--- list heap
    s = 0         # <--- index size

    q = parent(h, s)
    print (q)     # < prints the returned result (checkmark 1 showns which "None" is returned.
    p = q[1]
    #print (p)    # printing p would give you '1' value.

Sorry, I'm new to stackoverflow. I have updated my code – Simon Li Mar 23 '19 at 23:15 — Simon Li, Mar 23 '19 at 23:15

insert to max binary heap and ValueError

1 Answers1