Cola de prioridad en Python

Las colas de prioridad son estructuras de datos abstractas en las que cada dato/valor de la cola tiene una determinada prioridad. Por ejemplo, en las aerolíneas, el equipaje con título “Business” o “Primera clase” llega antes que el resto.
Priority Queue es una extensión de la cola con las siguientes propiedades.

1. Un elemento con prioridad alta se elimina de la cola antes que un elemento con prioridad baja.
2. Si dos elementos tienen la misma prioridad, se sirven según su orden en la cola.
   Varias aplicaciones de la cola de Prioridad en Informática son:
   algoritmos de Job Scheduling, CPU y Disk Scheduling, gestión de recursos que se comparten entre diferentes procesos, etc.

Diferencias clave entre Priority Queue y Queue:

1. En Queue, el elemento más antiguo se elimina primero. Mientras que, en Priority Queue, un elemento basado en la prioridad más alta se elimina de la cola.
2. Cuando los elementos se sacan de una cola de prioridad, el resultado obtenido se ordena en orden creciente o en orden decreciente. Mientras que, cuando los elementos se extraen de una cola simple, se obtiene un orden de datos FIFO en el resultado.

A continuación se muestra una implementación simple de la cola de prioridad.

# 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())

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. Una mejor implementación es usar Binary Heap , que normalmente se usa para implementar una cola de prioridad. Tenga en cuenta que Python también proporciona heapq en la biblioteca.

Time complexity: By using heap data structure to implement Priority Queues
Insert Operation: O(log(n))
Delete Operation: O(log(n))