from __future__ import annotations
from dataclasses import dataclass


@dataclass
class Heap :
    a:list[int]
    size:int

def crea_heap (capacity:int) -> Heap:
    #lista:list[int] = [0 for _ in range(capacity)]
    lista:list[int] = capacity * [10]
    return Heap (lista,0)


def left (i:int) -> int:
    return 2*i+1

def right (i:int) -> int:
    return 2*i+2

def parent (i:int) -> int:
    return (i-1)//2

def heap_insert (h: Heap, p:int) -> bool :
    if h.size==len(h.a):
        return False
    h.a[h.size]=p
    h.size += 1
    i = h.size-1
    while i>0 and h.a[i]>h.a[parent(i)] :
        h.a[i],h.a[parent(i)]=h.a[parent(i)], h.a[i]
        i = parent(i)
    return True

def get_max (h:Heap) -> int|None:
    if h.size==0 :
        return None
    else :
        return h.a[0]

def extract_max (h:Heap) -> int|None:
    if h.size==0 :
        return None 
    max = h.a[0]
    h.a[0] = h.a[h.size-1]
    h.size -= 1
    max_heapify(h,0)
    return max

def max_heapify (h:Heap, i:int) -> None:
    l = left(i)
    r = right(i)
    pos_max = i
    if l<h.size and h.a[l]>h.a[pos_max]:
        pos_max=l
    if r<h.size and h.a[r]>h.a[pos_max]:
        pos_max=r
    if pos_max != i :
        h.a[i], h.a[pos_max] = h.a[pos_max], h.a[i]
        max_heapify (h, pos_max)
        
def build_max_heap (a:list[int]) -> Heap:
    h = Heap (a, len(a))
    for i in range (parent(len(a)-1), -1, -1) :
        max_heapify (h, i)
    return h

def build_max_heap_fake (a:list[int]) -> Heap:
    h = crea_heap(len(a))
    for e in a :
         heap_insert(h, e)
    return h

def heap_sort (a:list[int]) -> None:
    h:Heap = build_max_heap(a)
    for i in range (len(a)-1, 0, -1):
        h.a[0], h.a[i]= h.a[i], h.a[0]
        h.size -= 1
        max_heapify (h, 0)

#h = build_max_heap ([3,30,2,5,7,80])

a = [3,30,2,5,7,80]
heap_sort(a)
print (a)