Heaps 1

#Daniel Bedialauneta
#Ejercicio 1
def flotar(h,x): #Supongo la primera posición reservada al numero de elementos
    h[0]+=1
    h.append(x)
    i=h[0]//2
    j=h[0]
    while i>0 and x>h[i]:
        h[j]=h[i]
        i=i//2
        j=j//2
    h[j]=x



"""
COMPLEJIDAD TEMPORAL
En un heap supongamos que hay k niveles, de 1 a k (no cuento el 0, cuento normal)
Si hay k niveles, hay (2^k)-1 nodos.
Y la cantidad de nodos es nuestro problema n, luego
n=(2^k)-1
Ahora bien, en esta función, el elemento que queremos hacer flotar,
como máximo, va a flotar a través de k niveles, las mismas veces que
se repite el while. Luego si intentamos tratar de despejar k, es decir,
el número de veces que se repite el while, tenemos:
n+1=2^k
log2(n+1)=k
El coste temporal de la función es:
t(n) = 1+k = 1+log2(n+1)
"""