Heaps 3

Daniel Bedialauneta
class Cola_Prioridad:



    def __init__(self,pri_f,MAX=-1):
        self.elems=[0] #Primera posición reservada al numero de elementos
        self.max=MAX
        self.pri=[None] ##Primera posición reservada al numero de elementos
        self.priority=pri_f

########################################################################

#Dejo aquí mi función flotar que uso como referencia en enqueue, pero no la llamo

    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

#Y aquí mi función del_maxheap que utilizo en dequeue como referencia, no la llamo

    def del_maxheap(h):
        maxheap=h[1] #Guardo el primer elemento para luego retornarlo
        x=h.pop() #Elimino el último elemento y lo guardo en x
        h[0]-=1 #Disminuyo en 1 el tamaño del heap
        i=1
        while 2*i<=h[0]: #Mientras el hijo de i esté en una posición menor o igual que el tamaño del heap
            if x>=h[2*i] and x>=h[2*i+1]: #Si x ya es mayor o igual que su hijos, salgo del ciclo
                break
            if 2*i+1>h[0]: #Para el caso en el que solo tenga un hijo al final y no se produzca index out of range
                h[i]=h[2*i]
                i=2*i
                break  #En realidad, este break no es necesario, ya que a este if solo entra en el último caso, pero bueno
            elif h[2*i]>h[2*i+1]:
                h[i]=h[2*i]
                i=2*i
            else:
                h[i]=h[2*i+1]
                i=2*i+1
        h[i]=x

########################################################################

    def enqueue(self,x): #Básicamente lo que he hecho es copiar mi función flotar de heap, adaptándola claro
        if self.isFull():
            return False
        p=self.priority(x)
        self.elems[0]+=1
        self.elems.append(x)
        self.pri.append(p)
        i=self.elems[0]//2
        j=self.elems[0]
        while i>0 and p>self.pri[i]:
            self.elems[j]=self.elems[i]
            self.pri[j]=self.pri[i]
            i=i//2
            j=j//2
        self.elems[j]=x
        self.pri[j]=p
        return True

    def dequeue(self):
        assert not self.isEmpty(), "Error en dequeue(): Cola de prioridad vacía"
        maxheap=self.elems[1]
        x=self.elems.pop()
        p=self.pri.pop()
        self.elems[0]-=1
        i=1
        while 2*i<=self.elems[0]:
            if p>=self.pri[2*i] and p>=self.pri[2*i+1]:
                break
            if 2*i+1>self.elems[0]:
                self.pri[i]=self.pri[2*i]
                self.elems[i]=self.elems[2*i]
                i=2*i
                break
            elif self.pri[2*i]>self.pri[2*i+1]:
                self.pri[i]=self.pri[2*i]
                self.elems[i]=self.elems[2*i]
                i=2*i
            else:
                self.pri[i]=self.pri[2*i+1]
                self.elems[i]=self.elems[2*i+1]
                i=2*i+1
        self.elems[i]=x
        self.pri[i]=p
        return maxheap

    def __len__(self):
        return self.elems[0]

    def isEmpty(self):
        return self.elems[0]==0

    def isFull(self):
        if self.max==-1:
            return False
        else:
            return self.elems[0]==self.max