class EmptyHeapException(Exception):
    pass
class Entry():
    ''' represents an entry that includes a key and a value'''
    def __init__(self, key, value):
        '''(Item, int, obj) -> NoneType
        constructs an item using key and value'''
        #repersentation invariant
        #_key is a posititve integer
        #_value is an object of any type
        self._key = key
        self._value = value
    def get_key(self):
        '''(Entry) ->int
        returns the key of this entry'''
        return self._key
    
    def get_value(self):
        '''(Entry) ->obj
        returns the value of this entry'''
        return self._value
    
    def __str__(self):
        '''(Entry) ->str
        returns a string representation  of this entry'''
        return "("+str(self._key)+", "+ str(self._value) + ")"
    
class Heap():
    ''' represents a heap, which is a complete binary tree, and satisfies 
    a heap-order, using a list.
    In this implelmentation, each node contains the keys only. 
    you complete this code by storing an entry (key, value) in each node.
    ''' 
    def __init__(self, root_entry):
        '''(eah, obj) -> NoneType
        construct a heap with root_entry as its root'''
        #representation invariant
        # _heap is a list
        # _heap[0] represents the root of the tree
        # _heap[0] has the highest priority
        # _heap[2*i + 1] represents the left child of the 
        #     node that stored at index i, and _heap[2*i + 1] >= _heap[i] 
        # _heap[2*i + 2] represents the right child of the 
        #     node that stored at index i, and _heap[2*i + 2] >= _heap[i]
        # _heap[len(_heap) -1] shows the last node
        # _heap[:] represents the result of traversing the tree by BFS, if not empty
        
        
        # append root_entry to a newly created empty list.
        self._heap = []
        self._heap.append(root_entry)
    
    def size(self):
        '''(Heap) -> int
        returns the number of nodes in the heap'''
        return len(self._heap)

    def is_empty(self):
        '''(Heap) -> bool
        returns True if this heap is empty'''
        return len(self._heap) == 0

    def remove_last_node(self):
        '''(Heap) -> Entry
        removes the last node from the heap and returns the entry stored in this node
        Raises: EmptyHeapException if this heap is empty'''
        if (self.is_empty()):
            raise EmptyHeapException("Heap is empty")
        return self._heap.pop(len(self._heap)-1)
    
    def min(self):
        '''(Heap) -> obj
        returns the entry with the highest priority
        Raises: EmptyHeapException'''
        if (self.is_empty()):
            raise EmptyHeapException("Heap is empty")
        return self._heap[0]

    def insert(self, entry):
        '''(Heap, Entry) -> NoneType
        insert the given entry at right place in the heap'''
        # step 1, 2, 3:  find the new last node, insert data, update last node
        # new last node is the element at len(self._heap)
        self._heap.append(entry)
        #step 3, restore heap-order
        self.upheap_bubbling()
    def upheap_bubbling (self):
        '''(Heap) -> None
        restores heap order by swaping the entries along an upward path from inserted node'''
        # find the last node index
        cur = len(self._heap)-1
        # find the parent (always  (last_node - 1//2) because it rounded down)
        parent = (cur -1 )//2
        # continue swapping until last node in right place or you get to the root
        while (cur > 0 and self._heap[parent].get_key() > self._heap[cur].get_key()):
            self._heap[parent] , self._heap[cur] = self._heap[cur] , self._heap[parent]
            # update cur and parent
            cur = parent
            parent = (cur -1 )//2
            
    def extract_min(self):
        '''(Heap) -> Entry
        removes the highest priority Entry and return it.
        Raises: EmptyHeapException
        '''
        # raise an exception if heap is empty
        if (self.is_empty()):
            raise EmptyHeapException ("Heap is empty")
        # step 1: get the entry with minimum key 
        min_value = self._heap[0]
        # remove the last node
        l_node = self._heap.pop(len(self._heap) -1)
        # step2: replace the root with last node if at least there is one entry in the heap
        if(len(self._heap) != 0):
            # replace teh root with the last node
            self._heap[0] = l_node
            # step 3, 4: last node will be updated automatically, so restore the heap_order
            self.downheap_bubbling()
        # return the highest priority item
        return min_value
    
    def downheap_bubbling(self):
        '''(Heap) -> NoneType
        restore the heap order by swapping the entries down the path'''
        # start from the root
        cur = 0
        # continue going down while heap order is violated
        while (self.violates(cur)):
            # find the index of the child which contains smaller data/ violates heap order
            child_index = self.find_index(cur)
            # swap data at cur and data at child
            self._heap[cur] , self._heap[child_index] = self._heap[child_index] , self._heap[cur]
            # update cur to point to child_index
            cur = child_index
    def violates(self, index):
        '''(Heap, index) -> bool
        checks if the given index has a key greater than one of its children'''
        # get left and right child index
        left = index * 2 + 1
        right = index * 2 + 2
        # raise a flag as an indicator of the violation
        violates = True
        # if cur index points to a leaf, it does not violate the heap order. a leaf is a node whose left child index is greater than the heap's length
        if (left >= len(self._heap)):
            violates = False
        # otherwise, it may have one child. since the heap is a complete tree, therfore it has a left child, which means the index to right child is >= than the heap's length. In this case we check the left child for the violation of heap-order
        elif (right >= len(self._heap)):
            violates = self._heap[index].get_key() > self._heap[left].get_key()
        #otherwise, it has two children, therefore you need to check both the children 
        else:
            violates = (self._heap[index].get_key() > self._heap[left].get_key()) or (self._heap[index].get_key() > self._heap[right].get_key())
        return violates
    def find_index(self, index): 
        '''(Heap, int) -> int
        return the index where it violates the heap order'''
        # find left and right child and initialize returned index
        left = index * 2 + 1
        right = index * 2 + 2
        returned_index = 0
        #if it has one child, it is left child. which means right child's index >= len of heap
        if (right >= len (self._heap)):
            returned_index = left
        # otherwise, we should find which one of its children has smaller data
        elif (self._heap[left].get_key() < self._heap[right].get_key()):
            returned_index = left
        else:
            returned_index = right
        #return the found index
        return returned_index
        
    def BFS(self):
        '''(BT) -> str
        traverse the tree in Breadth First search mehtod
        '''
        # remove all Nones from the list
        result = ""
        for item in self._heap:
            if (item is not None):
                result = result + " " + str(item)
        return result
        
        

    

    
    

if (__name__ == "__main__"):
    ''' construct  a priority queue using a heap
    containing these keys:
    (95, 'A'), (40, 'B'), (55, 'C'), (60, 'D'), (20, 'E'), (50, 'F'), (85, 'G')
    '''
    a = Entry(95, 'A')
    b = Entry(40, 'B')
    c = Entry(55, 'C')
    d = Entry(60, 'D')
    e = Entry(20, 'E')
    f = Entry(50, 'F')
    g = Entry(85, 'G')
    heap = Heap(a)
    heap.insert(b)
    heap.insert(c)
    heap.insert(d)
    heap.insert(e)
    heap.insert(f)
    heap.insert(g)
        
    print(heap.BFS())
    
    print(heap.extract_min())
    print(heap.BFS())
    print(heap.extract_min())
    print(heap.BFS())
    print(heap.extract_min())
    print(heap.BFS())
    print(heap.extract_min())
    print(heap.BFS())
    print(heap.extract_min())
    print(heap.BFS())
    print(heap.extract_min())
    print(heap.BFS())
    print(heap.extract_min())
    print(heap.BFS())
    """this should raise an exception
    print(heap.extract_min())
    """