Prioridad 3

#Daniel Bedialauneta
#EJERCICIO 3 COLA PRIORIDAD

class Cola_Prioridad:

    def __init__(self, pri_f, MAX=8):
        self.elems = [None]*MAX
        self.priority = pri_f # pri_f(x) devuelve un entero, cp descendente
        self.head = 0
        self.q = -1
        self.nelems = 0
        self.size = MAX

    def enqueue(self,x):
        if self.isFull():
            return False
        p=self.priority(x)
        i=0
        j=self.nelems-1
        while i<=j:
            m=(i+j)//2
            y=self.elems[(self.head+m)%self.size]
            if p>self.priority(y):
                j=m-1
            elif p<self.priority(y):
                i=m+1
            else:
                break
        if i>j:
            m=i
        if m<self.nelems//2:
            for i in range(m):
                read_pos=(self.head+i)%self.size
                write_pos=(read_pos-1)%self.size
                self.elems[write_pos]=self.elems[read_pos]
            self.head=(self.head-1)%self.size
        else:
            for i in range(self.nelems-1,m-1,-1):
                read_pos=(self.head+i)%self.size
                write_pos=(read_pos+1)%self.size
                self.elems[write_pos]=self.elems[read_pos]
            self.q=(self.q+1)%self.size
        self.elems[(self.head+m)%self.size]=x
        self.nelems+=1
#Coste t(MAX)=log(MAX)+m, donde log es en base 2 y m es la cantidad de posiciones que hay de self.head
#a la posición donde se debe insertar el elemento. Este m no va a ser mayor que MAX/2.
#PEOR CASO: se completa el while hasta i>j, es decir, ya tenemos log(MAX) y luego m=(MAX//2)+1 o m=(MAX//2)-1,
#en tal caso, el coste es t(MAX)=MAX//2+log(MAX)
#MEJOR CASO: que m=0, es decir, el elemento que vamos a insertar tiene más prioridad que cualquier otro, y
#se va a colocar a la cabeza. En tal caso, t(MAX)=log(MAX)

    def dequeue(self):
        assert not self.isEmpty(), "Error en deq(): Cola de prioridad vacía"
        x=self.elems[self.head]
        self.head=(self.head+1)%self.size
        self.nelems-=1
        return x
#Coste fijo

    def __len__(self):
        return self.nelems
#Coste fijo

    def isEmpty(self):
        return self.nelems == 0
#Coste fijo

    def isFull(self):
        return self.nelems==self.size
#Coste fijo