heap_sort.py

"""
ПРИНЦИП РАБОТЫ
    Этап 1.
        Формируем из всего массива сортирующее дерево.
        Для этого проходим справа-налево элементы (от последних к первым) и если у элемента есть потомки,
        то для него делаем просейку.
    Этап 2.
        Максимумы ставим в конец неотсортированной части массива.
        Так как данные в массиве после первого этапа представляют из себя сортирующее дерево,
        максимальный элемент находится на первом месте в массиве.
        Первый элемент (он же максимум) меняем с последним элементом неотсортированной части массива местами.
        После этого обмена максимум оказался своём окончательном месте, т.е. максимальный элемент отсортирован.
        Неотсортированная часть массива перестала быть сортирующим деревом, но это исправляется однократной просейкой —
        в результате чего на первом месте массива оказывается предыдущий по величине максимальный элемент.
        Действия этого этапа снова повторяются для оставшейся неупорядоченной области,
        до тех пор пока максимумы поочерёдно не будут перемещены на свои окончательные позиции.

    Статья - https://habr.com/ru/company/edison/blog/495420/.

ВРЕМЕННАЯ СЛОЖНОСТЬ
    Что касается сложности по времени, то она зависит от просейки. Однократная просейка обходится в O(log(n)).
    Сначала мы для n элементов делаем просейку, чтобы из массива построить первоначальную кучу — O(nlog(n)).
    На втором этапе мы при вынесении n текущих максимумов из кучи делаем однократную просейку
    для оставшейся неотсортированной части, т.е. этот этап также стоит нам O(nlog(n)).
    Итоговая сложность по времени: O(nlog(n)) + O(nlog(n)) = O(nlog(n)).

    При этом у пирамидальной сортировки нет ни вырожденных ни лучших случаев.
    Любой массив будет обработан на приличной скорости, но при этом не будет ни деградации ни рекордов.

Сортировка кучей в среднем работает несколько медленнее чем быстрая сортировка. Но для quicksort можно подобрать массив-убийцу, на котором компьютер зависнет, а вот для heapsort — нет.
    Вики - https://ru.wikipedia.org/wiki/Пирамидальная_сортировка.

ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ
    Чем хороша простая куча — её не нужно отдельно хранить, в отличие от других видов деревьев
    (например, двоичное дерево поиска на основе массива прежде чем использовать нужно сначала создать).
    Любой массив уже является деревом, в котором прямо на ходу можно сразу определять родителей и потомков.
    Сложность по дополнительной памяти O(1), всё происходит сразу на месте.
"""
from dataclasses import dataclass


@dataclass(frozen=True)
class User:
    __slots__ = ['username', 'solved', 'errors']
    username: str
    solved: int
    errors: int

    def key(self):
        return -self.solved, self.errors, self.username

    def __gt__(self, other):
        return self.key() > other.key()

    def __lt__(self, other):
        return other > self

    def __str__(self):
        return self.username


def heapsort(data):
    for start in range((len(data)-2)//2, -1, -1):
        heapsift(data, start, len(data) - 1)

    for end in range(len(data)-1, 0, -1):
        data[end], data[0] = data[0], data[end]
        heapsift(data, 0, end - 1)


def heapsift(data, start, end):
    root = start

    while True:
        child = root * 2 + 1

        if child > end:
            break

        if child + 1 <= end and data[child] < data[child+1]:
            child += 1

        if data[root] < data[child]:
            data[root], data[child], root = data[child], data[root], child
        else:
            break


n = int(input())
users = []

for _ in range(n):
    username, solved, errors = input().split()
    users.append(User(username, int(solved), int(errors)))

heapsort(users)

for person in users:
    print(person)