class Heap:

    def __init__(self):
        self.data = []

    def _swap(self, i, j):
        self.data[i], self.data[j] = self.data[j], self.data[i]

    def _parent(self, i):
        return (i-1) // 2

    def _left_child(self, i):
        return 2 * i + 1

    def _right_child(self, i):
        return 2 * i + 2

    def add(self, x):
        self.data.append(x)
        a = len(self.data) - 1
        while a > 0 and self.data[a] < self.data[self._parent(a)]:
           self._swap(a, self._parent(a))
           a = self._parent(a)

    def getmin(self):
        return self.data[0]

    def popmin(self):
        self.data[0] = self.data[-1]
        self.data.pop()
        a = 0
        while True:
            m = a
            if self._left_child(a) < len(self.data) and \
                self.data[self._left_child(a)] < self.data[m]:
                m = self._left_child(a)
            if self._right_child(a) < len(self.data) and \
                self.data[self._right_child(a)] < self.data[m]:
                m = self._right_child(a)
            if m > a:
                self._swap(a, m)
                a = m
            else:
                return


def heapsort(data):
    tmp = Heap()
    sorted_data = []
    for element in data:
        tmp.add(element)
    for i in range(len(data)):
        sorted_data.append(tmp.getmin())
        tmp.popmin()
    return sorted_data


print(heapsort([6, 9, 34, 1, 6, 40, 67, 9]))