heapsort.py

import random


def heapsort(data: list) -> list:
    data = heapify_array(data)

    for i in range(len(data) - 1, -1, -1):
        data[i], data[0] = data[0], data[i]
        data[:i] = heapify(data[:i], 0)

    return data


def heapify_array(data: list) -> list:
    n = int(len(data) / 2)

    for i in range(n, -1, -1):
        heapify(data, i)

    return data


def heapify(data: list, i: int) -> list:
    left = 2 * i + 1
    right = 2 * i + 2
    j = i
    n = len(data)

    if left < n and data[left] > data[i]:
        j = left
    if right < n and data[right] > data[j]:
        j = right

    if i is not j:
        data[i], data[j] = data[j], data[i]
        data = heapify(data, j)

    return data


def main():
    data = [x for x in range(10)]
    random.shuffle(data)

    print(f"Data bevor sorting: {data}")
    print(f"Data after sorting: {heapsort(data)}")


if __name__ == "__main__":
    main()