Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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
Add Comment
Please, Sign In to add comment