"""
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
        """
        if self.size() == 0:
            return None
        else:
            return self.items[1]

    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]
        """
        if self.size() > 0:
            # swap first and last item
            self.swap(1, self.size())

            # delete last item and reapair
            self.items.pop()
            self.repair_downwards(1)

    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 swap(self, index1, index2):
        """
        Swap elements in array at the given positions and adjust heap index
        """
        self.items[index1], self.items[index2] = \
            self.items[index2], self.items[index1]

    def repair_upwards(self, index):
        """
        Repair min-heap property upwards, starting from the given position.
        """
        while index > 1:
            parent = index // 2
            if self.items[parent].key <= self.items[index].key:
                break
            self.swap(parent, index)
            index = parent

    def repair_downwards(self, index):
        """
        Repairs the min-heap property at node index against its children.
        """
        while 2*index <= self.size():
            index_left_child = 2*index
            index_right_child = 2*index+1

            # find min-key in children
            index_min_child = index_left_child
            if index_right_child <= self.size():
                if self.items[index_left_child].key > self.items[index_right_child].key:  # noqa
                    index_min_child = index_right_child

            # swap min-key with parent
            if self.items[index].key <= self.items[index_min_child].key:
                break
            self.swap(index, index_min_child)
            index = index_min_child


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)


def heapsort(a):
    """
    Implementation of Heapsort
    >>> heapsort([12, 7, 13, 1, 24, 5, 9])
    [1, 5, 7, 9, 12, 13, 24]
    """
    h = BinaryHeap()
    h.create()
    n = len(a)
    for i in range(0, n):
        h.insert(a[i], a[i])
    for i in range(0, n):
        min_key = h.get_min().key
        a[i] = min_key
        h.delete_min()
    return a