6.5.7

#Daniel Bedialauneta
# h: lista de números, h[0] no se usa ==> n=len(h)-1

def heapify(h):
    for k in range(2,len(h)): #n-1 repeticiones
        j=k
        i=k//2
        item=h[k]
        #1
        while i>0 and h[i]<item: #s iteraciones
            h[j]=h[i]
            j=i
            i=i//2
            #1
        h[j]=item #1

"""
i=subíndice
j=subíndice
i,j no tienen nada que ver con los i,j de la función
n-1=número de repeticiones del for
Si=número de repeticiones del while para cada posición k (para cada subíndice i)

t(n)=(Suma:i=1 -> n-1)[1+(Suma: j=1 -> Si)(1)+1]=

= (Suma:i=1 -> n-1)[(Suma: j=1 -> Si)(1)+2]

Esto es, en cada i se suma un Si+2. Si depende de i.


Mejor caso: que la lista h venga ya ordenada de mayor a menor (sin contar la posición 0)
En tal caso, el contenido del while nunca se va a ejecutar, solo sus condiciones.
Por tanto, podriamos escribir
t(n) = (Suma:i=1 -> n-1)[3] = 3*(n-1) = 3n-1
Es decir, en el mejor caso, t(n) está en O(n)


Peor caso: no estoy seguro, pero creo que el peor caso es que la lista te venga de menor a mayor y con todos los elementos diferentes (sin tenener en cuenta la posición 0)
En este caso, nos da igual la condición h[i]<item, porque siempre se va a cumplir.
Así que
t(n)=(Suma:i=1 -> n-1)[(Suma: j=1 -> Si)(1)+2] nos queda, porque (Suma: j=1 -> Si)(1)=Si=i//2

t(n)=(Suma:i=1 -> n-1)(i//2+2)

Para dos i's consecutivos el primero par y el segundo impar, i//2+2 es lo mismo. Ejemplo:
i=4, (4//2)+2=2+2=4
i=5, (5//2)+2=2+2=4
O sea que en vez de hacer la suma de i=1 a n-1, la hacemos hasta la mitad, y cada elemento que sumamos lo multiplicamos por 2. Nos queda:
t(n) = (Suma:i=1 -> n-1)(i//2+2) = (1//2)+2+(Suma:i=2 -> n-1)(i//2+2) (por ser el primer i impar)
1//2=0
t(n) = (1//2)+2+(Suma:i=2 -> n-1)(i//2+2) = 0+2+(Suma:i=1 -> (n-1)//2)(2*i+4)+delta(n-1 par)*((n-1)//2+2) = ... no sé qué da, pero algo así

t(n)= p*n^2+..., es decir, t(n) está en O(n^2)