File d'attente prioritaire en Python
Files d'attente prioritaires sont des structures de données abstraites où chaque donnée/valeur dans la file d'attente a une certaine priorité. Par exemple, dans les compagnies aériennes, les bagages portant le titre Business ou First class arrivent plus tôt que les autres.
La file d'attente prioritaire est une extension de la file d'attente avec les propriétés suivantes.
- Un élément de priorité élevée est retiré de la file d'attente avant un élément de priorité faible.
- Si deux éléments ont la même priorité, ils sont servis selon leur ordre dans la file d'attente.
Divers applications de la file d'attente prioritaire en informatique sont :
Algorithmes de planification des tâches, planification du processeur et des disques, gestion des ressources partagées entre différents processus, etc.
Principales différences entre la file d'attente prioritaire et la file d'attente :
- Dans la file d'attente, l'élément le plus ancien est retiré en premier de la file d'attente. Tandis que, dans la file d'attente prioritaire, un élément basé sur la priorité la plus élevée est retiré de la file d'attente.
- Lorsque des éléments sont retirés d'une file d'attente prioritaire, le résultat obtenu est soit trié par ordre croissant, soit par ordre décroissant. Tandis que, lorsque des éléments sont extraits d'une simple file d'attente, un ordre FIFO des données est obtenu dans le résultat.
Ci-dessous se trouve un mise en œuvre simple de la file d'attente prioritaire.
Python
# 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())> |
Sortir:
12 1 14 7 14 12 7 1
Notez que la complexité temporelle de la suppression est O(n) dans le code ci-dessus. UN meilleure mise en œuvre est d'utiliser Tas binaire qui est généralement utilisé pour implémenter une file d’attente prioritaire. Notez que Python fournit tas à la bibliothèque également.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
