Cola de prioridad en Python
Colas prioritarias son estructuras de datos abstractas donde cada dato/valor en la cola tiene una cierta prioridad. Por ejemplo, en las aerolíneas el equipaje con el título Business o First-class llega antes que el resto.
Priority Queue es una extensión de la cola con las siguientes propiedades.
- Un elemento con alta prioridad se retira de la cola antes que un elemento con baja prioridad.
- Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola.
Varios aplicaciones de la cola de Prioridad en Informática son:
Algoritmos de programación de trabajos, programación de CPU y disco, gestión de recursos que se comparten entre diferentes procesos, etc.
Diferencias clave entre cola prioritaria y cola:
- En la cola, el elemento más antiguo se retira primero de la cola. Mientras que, en la cola de prioridades, un elemento basado en la prioridad más alta se retira de la cola.
- Cuando los elementos salen de una cola de prioridad, el resultado obtenido se ordena en orden creciente o en orden decreciente. Mientras que, cuando se extraen elementos de una cola simple, se obtiene un orden FIFO de datos en el resultado.
A continuación se muestra un implementación simple de la cola de prioridad.
Pitón
# A simple implementation of Priority Queue> # using Queue.> class> PriorityQueue(> object> ):> > def> __init__(> self> ):> > self> .queue> => []> > def> __str__(> self> ):> > return> ' '> .join([> str> (i)> for> i> in> self> .queue])> > # for checking if the queue is empty> > def> isEmpty(> self> ):> > return> len> (> self> .queue)> => => 0> > # for inserting an element in the queue> > def> insert(> self> , data):> > self> .queue.append(data)> > # for popping an element based on Priority> > def> delete(> self> ):> > try> :> > max_val> => 0> > for> i> in> range> (> len> (> self> .queue)):> > if> self> .queue[i]>> self> .queue[max_val]:> > max_val> => i> > item> => self> .queue[max_val]> > del> self> .queue[max_val]> > return> item> > except> IndexError:> > print> ()> > exit()> if> __name__> => => '__main__'> :> > myQueue> => PriorityQueue()> > myQueue.insert(> 12> )> > myQueue.insert(> 1> )> > myQueue.insert(> 14> )> > myQueue.insert(> 7> )> > print> (myQueue)> > while> not> myQueue.isEmpty():> > print> (myQueue.delete())> |
Producción:
12 1 14 7 14 12 7 1
Tenga en cuenta que la complejidad temporal de la eliminación es O (n) en el código anterior. A mejor implementación es usar montón binario que normalmente se utiliza para implementar una cola de prioridad. Tenga en cuenta que Python proporciona montónq en la biblioteca también.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
