"""
Binary Heap (Array-Implementation)
Copyright 2022, University of Freiburg
Marc Fuchs <marc.fuchs@cs.uni-freiburg.de>
"""


class BinaryHeap:
    """ An Array-Implementation of a Binary Heap as explained in lecture 9 """

    def create(self):
        """
        Creates the array 'items' storing all items.
        For simplification, indices of stored items range from 1 to n.
        (Position 0 will always be None)
        """
        self.items = [None]

    def size(self):
        """
        Number of items in Heap.

        >>> h = BinaryHeap()
        >>> h.create()
        >>> h.size()
        0
        """
        return len(self.items) - 1

    def __repr__(self):
        """
        A heap in human-readable form.
        Each item is represented together with its position
        in the array. For instance, if the item has key '3',
        value 'a' and is located at position '6',
        its representation is '3:a@6'
        """
        representation = []
        for i, item in enumerate(self.items):
            representation.append(str(item) + "@" + str(i))
        return "[" + ", ".join(representation) + "]"

    def get_min(self):
        """ Get item with minimal key.

        >>> h = BinaryHeap()
        >>> h.create()
        >>> h.insert(3, "A")
        >>> h.insert(7, "Q")
        >>> h.insert(2, "F")
        >>> h.insert(1, "M")
        >>> h.insert(4, "Y")
        >>> h.get_min()
        1:M
        """
        pass # Add your code here

    def delete_min(self):
        """ Delete item with minimal Key

        >>> h = BinaryHeap()
        >>> h.create()
        >>> h.insert(3, "A")
        >>> h.insert(7, "Q")
        >>> h.insert(2, "F")
        >>> h.insert(1, "M")
        >>> h.insert(4, "Y")
        >>> h.delete_min()
        >>> h
        [None@0, 2:F@1, 4:Y@2, 3:A@3, 7:Q@4]
        """
        pass # Add your code here

    def insert(self, key, value):
        """
        Insert HeapItem to Heap with given value and key.
        >>> h = BinaryHeap()
        >>> h.create()
        >>> h.insert(3, "A")
        >>> h.insert(7, "Q")
        >>> h.insert(2, "F")
        >>> h.insert(1, "M")
        >>> h.insert(4, "Y")
        >>> h
        [None@0, 1:M@1, 2:F@2, 3:A@3, 7:Q@4, 4:Y@5]
        """
        item = HeapItem(key, value)
        self.items.append(item)
        self.repair_upwards(self.size())

    def repair_upwards(self, index):
        """
        Repair min-heap property upwards, starting from the given position.
        """
        pass # Add your code here

    def repair_downwards(self, index):
        """
        Repairs the min-heap property at node index against its children.
        """
        pass # Add your code here


class HeapItem:
    """ An item of the Binary Heap, containing key and value. """

    def __init__(self, key, value):
        self.key = key
        self.value = value

    def __repr__(self):
        """
        A heap item in human-readable form.
        For example, show element with key '3' and value
        'a' is 3:a.
        """
        return "%d:%s" % (self.key, self.value)