#!/usr/bin/env python3

import random


class Heap(object):

    __array = []

    def __init__(self, length):
        self.__array = [0] * (length + 1)

    def get_size(self):
        return self.__array[0]

    def set_size(self, n):
        self.__array[0] = n

    def set(self, ind, elem):
        self.__array[ind] = elem

    def get(self, ind):
        return self.__array[ind]

    def __str__(self):
        res = ""
        if self.get_size() > 0:
            for i in range(1, self.get_size()+1):
                res += str(self.__array[i]) + ' '
        return res

    def left(self, root):
        return 2*root

    def right(self, root):
        return 2*root + 1

    def parent(self, child):
        return child // 2

    def inside(self, ind):
        return (ind >= 1) and (ind <= self.get_size())

    def move_up(self, i):
        j = self.parent(i)
        if self.inside(j):
            if self.get(i) > self.get(j):
                tmp = self.get(i)
                self.set(i, self.get(j))
                self.set(j, tmp)
                self.move_up(j)

    def move_down(self, i):
        j = self.left(i)
        if self.inside(j):
            k = self.right(i)
            if self.inside(k):
                if self.get(k) > self.get(j):
                    j = k
            if self.get(i) < self.get(j):
                tmp = self.get(i)
                self.set(i, self.get(j))
                self.set(j, tmp)
                self.move_down(j)

    def take_max(self):
        res = self.get(1)
        self.set(1, self.get(self.get_size()))
        self.set_size(self.get_size()-1)
        self.move_down(1)
        return res

    def add_to_heap(self, elem):
        if self.get_size() < len(self.array) - 1:
            self.set_size(self.get_size() + 1)
            self.set(self.get_size(), elem)
            self.move_up(self.get_size())
        else:
            raise ValueError('ei mahu')

    def make_heap(self, i):
        if i <= self.get_size():
            self.make_heap(self.left(i))
            self.make_heap(self.right(i))
            self.move_down(i)

    @staticmethod
    def heapsort(sarray):
        n = len(sarray)
        if n < 2:
            return
        hp = Heap(n)
        hp.set_size(n)
        for i in range(1, n+1):
            hp.set(i, sarray[i-1])
        hp.make_heap(1)
        for k in range(n-1, -1, -1):
            last = hp.take_max()
            sarray[k] = last


def main():
    n = 6
    numbers = []
    for i in range(n):
        numbers.append(random.randint(0, 9))
    print(numbers)
    Heap.heapsort(numbers)
    print(numbers)


if __name__ == '__main__':
    main()