'''
CSC263 Winter 2019
Problem Set 1 Starter Code
University of Toronto Mississauga
'''

# Do NOT add any "import" statements
#Parent(i) = floor(i/2)
#Right(i) = 2i + 1
#Left(i) = 2i

def assign_variable(lst,val):
    if val > len(lst)-1 or val < 0:
        return 0
    return val

def smallest_child(lst,index):
    left_child = assign_variable(lst,index*2)
    right_child = assign_variable(lst,index*2 + 1)
    return_child = left_child

    #incase the right child is smaller
    if lst[right_child] < lst[left_child]:
        return_child = right_child

    return return_child

def bubble_up(lst,index):
    root = assign_variable(lst,index//2)
    if lst[root] > lst[index]: #Checks if the parent is greater than the child
        #Since it is a min heap we must keep the smaller number at the root
        lst[root], lst[index] =  lst[index], lst[root] #performs the swap
        bubble_up(lst,root)
    return


def bubble_down(lst,index):

    lowest_child = smallest_child(lst,index)

    #check if the child is smaller than the root, if so we swap
    if lst[lowest_child] < lst[index]:
        lst[index], lst[lowest_child] = lst[lowest_child], lst[index]
        #recursive call incase there needs to be more bubbling down
        bubble_down(lst, lowest_child)
    return


def insert(lst,val):
    lst.append(val)
    bubble_up(lst, len(lst)-1)
    return

def get_min(lst,counter):
    level = 1 # start at first level
    target = 0 #keep track of the index
    while level != counter:
        target = smallest_child(lst,target)
        level += 1

    return lst[target]





def solve_moving_min(commands):
    '''
    Pre: commands is a list of commands
    Post: return list of get_min results
    '''
    lst = []
    results = []
    counter = 0
    for words in commands:
        if words == 'get_min':
            counter += 1
            results.append(get_min(lst, counter))
        else:
            parsed_word = words.split()
            insert(lst,parsed_word[1])
    return


if __name__ == '__main__':

    # some small test cases
    # Case 1
    assert [10, 5, 10] == solve_moving_min(
    ['insert 10',
     'get_min',
     'insert 5',
     'insert 2',
     'insert 50',
     'get_min',
     'get_min',
     'insert -5'
    ])