Prioritaire wachtrijen zijn abstracte datastructuren waarbij elke data/waarde in de wachtrij een bepaalde prioriteit heeft. Bij luchtvaartmaatschappijen komt bagage met de titel Business of First Class bijvoorbeeld eerder aan dan de rest.
Prioriteitswachtrij is een uitbreiding van de wachtrij met de volgende eigenschappen.
datastructuren in Java
- Een element met hoge prioriteit wordt uit de wachtrij gehaald vóór een element met lage prioriteit.
- Als twee elementen dezelfde prioriteit hebben, worden ze geserveerd volgens hun volgorde in de wachtrij.
Verscheidene toepassingen van de Prioriteitswachtrij in Computerwetenschappen zijn:
Algoritmen voor taakplanning, CPU- en schijfplanning, beheer van bronnen die worden gedeeld tussen verschillende processen, enz.
Belangrijkste verschillen tussen Prioriteitswachtrij en Wachtrij:
- In Queue wordt het oudste element als eerste uit de wachtrij gehaald. Terwijl in Priority Queue een element op basis van de hoogste prioriteit uit de wachtrij wordt gehaald.
- Wanneer elementen uit een prioriteitswachtrij worden gehaald, wordt het verkregen resultaat in oplopende volgorde of in afnemende volgorde gesorteerd. Terwijl, wanneer elementen uit een eenvoudige wachtrij worden gehaald, een FIFO-volgorde van gegevens in het resultaat wordt verkregen.
Hieronder staat een eenvoudige implementatie van de prioriteitswachtrij.
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())> |
>
nfa naar dfa
>Uitgang:
12 1 14 7 14 12 7 1>
Merk op dat de tijdscomplexiteit van het verwijderen O(n) is in de bovenstaande code. A betere implementatie is te gebruiken Binaire hoop die doorgaans wordt gebruikt om een prioriteitswachtrij te implementeren. Merk op dat Python dit biedt hoopq ook in de bibliotheek.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))>