Structures_last

class StackWithMaxElement:
    # Надо сделать универсально что бы можно было задавать параметром с максимумом или с минимумом
    def __init__(self):
        self.items = []
        self.max = []

    def push(self, item):
        self.items.append(int(item))
        if len(self.max) == 0:
            self.max.append(item)
        elif item >= self.max[-1]:
            self.max.append(item)

    def pop(self):
        tmp = self.items.pop()
        if tmp == self.max[-1]:
            self.max.pop()
        return tmp

    def get_max(self):
        return self.max[-1]

    def is_empty(self):
        return len(self.items) == 0

    def clear(self):
        self.items.clear()


class QueueWithMaxElement:
    def __init__(self):
        self.stack1 = StackWithMaxElement()
        self.stack2 = StackWithMaxElement()

    def push(self, item):
        self.stack1.push(item)

    def pop(self):
        if self.stack2.is_empty():
            while not self.stack1.is_empty():
                self.stack2.push(self.stack1.pop())
        return self.stack2.pop()

    def get_max(self):
        if self.stack1.is_empty():
            return self.stack2.get_max()
        elif self.stack2.is_empty():
            return self.stack1.get_max()
        else:
            return max(self.stack1.get_max(), self.stack2.get_max())


class Heap:
    def __init__(self, dimension=2, modifier='maximum'):
        self.items = []
        self.size = 0
        self.d = dimension
        self.modifier = modifier

    def get_parent_index(self, index):
        return (index-1)/self.d

    def get_children_indices(self, index):
        tmp = []
        for i in range(self.d):
            tmp.append(self.d * index + i + 1)
        return tmp

    def sift_up(self, index):
        tmp_index = get_parent_index(index)
        while index > 0 and self.items[tmp_index] < self.items[index]:
            tmp = self.items[tmp_index]
            self.items[tmp_index] = self.items[index]
            self.items[index] = tmp
            index = tmp_index

    def sift_down(self, index):
        max_index = index
        children_indices = get_children_indices(index)
        for i in children_indices:
            if i <= size and self.items[i] > self.items[max_index]:
                max_index = i
        if index != max_index:
            tmp = self.items[max_index]
            self.items[max_index] = self.items[index]
            self.items[index] = tmp
            sift_down(max_index)

    def insert(self, priority):
        self.size += 1
        self.items[self.size] = priority
        sift_up(self.size)

    def extract_max(self):
        res = self.items[0]
        self.items[0] = self.items[self.size]
        self.size -= 1
        sift_down(0)
        return res

    def remove(self, index):
        res = self.items[index]
        self.items[index] = self.items[self.size]
        self.size -= 1
        sift_down(index)
        return res

    def change_priority(self, index, priority):
        old_p = self.items[index]
        self.items[index] = priority
        if priority > old_p:
            sift_up(index)
        else:
            sift_down(index)


def heap_sort(array):
    heap = Heap()
    for i in range(len(array)):
        heap.insert(array[i])
    for i in range(len(array), 0, -1):
        array[i] = heap.extract_max()