3.zadanie

class Item:
    def __init__(self, value):
        self.value = value
        self.next = None

class Node:
    def __init__(self, key, value):
        self.key = key
        self.value_list = Item(value)
        self.left = self.right = None

class PriorityQueue:
    def __init__(self):
        self.root = None

    def add(self, key, value):
        if self.root is None:
            self.root = Node(key, value)
            return
        node = self.root
        while True:
            if key == node.key:
                item = node.value_list
                while item.next is not None:
                    item = item.next
                item.next = Item(value)
                break
            if key > node.key:
                if node.right is None:
                    node.right = Node(key, value)
                    break
                node = node.right
            if key < node.key:
                if node.left is None:
                    node.left = Node(key, value)
                    break
                node = node.left

    def is_empty(self):
        return self.root is None

    def min(self):
        if self.root is None:
            raise EmptyError
        node = self.root
        while node.left is not None:
            node = node.left
        return node.key, node.value_list.value

    def remove_min(self):
        if self.root is None:
            raise EmptyError
        node = self.root
        rodic = None
        while node.left:
            rodic = node
            node = node.left

        if node.value_list.next:
            value = node.value_list.value
            node.value_list = node.value_list.next
            return node.key, value
        else:
            if node.right is None:
                if rodic is None:
                    vrat = node.key, node.value_list.value
                    self.root = None
                    return vrat
                vrat = node.key, node.value_list.value
                rodic.left = None
                return vrat
            else:
                vrat = node.key, node.value_list.value
                node = node.right
                if rodic:
                    rodic.left = node
                else:
                    self.root = node
                return vrat

    def __len__(self):
        if self.root is None:
            return 0
        stack = [self.root]
        pocet = 0
        while stack:
            node = stack.pop()
            zoznam = node.value_list
            while zoznam:
                pocet += 1
                zoznam = zoznam.next
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return pocet

    def tree_height(self):
        def height_rek(node):
            if node is None or node.left is None and node.right is None:
                return 0
            lavy = height_rek(node.left)
            pravy = height_rek(node.right)
            return 1 + max(lavy, pravy)
        if self.root is None:
            return -1
        return height_rek(self.root)

def pq_sort(pole):
    pq = PriorityQueue()
    for key, value in pole:
        pq.add(key, value)
    for i in range(len(pole)):
        pole[i] = pq.remove_min()