Prioritní fronta v Pythonu
Prioritní fronty jsou abstraktní datové struktury, kde každá data/hodnota ve frontě má určitou prioritu. Například u leteckých společností dorazí zavazadla s názvem Business nebo First-class dříve než ostatní.
Prioritní fronta je rozšířením fronty s následujícími vlastnostmi.
- Prvek s vysokou prioritou je vyřazen z fronty před prvkem s nízkou prioritou.
- Pokud mají dva prvky stejnou prioritu, jsou obsluhovány podle pořadí ve frontě.
Rozličný aplikací z fronty priorit v informatice jsou:
Algoritmy plánování úloh, plánování CPU a disku, správa zdrojů, které jsou sdíleny mezi různými procesy atd.
Hlavní rozdíly mezi prioritní frontou a frontou:
- Ve frontě je nejstarší prvek vyřazen z fronty jako první. Zatímco ve frontě priority je prvek založený na nejvyšší prioritě vyřazen z fronty.
- Když prvky vyskočí z prioritní fronty, získaný výsledek se seřadí buď v rostoucím pořadí, nebo v sestupném pořadí. Zatímco při vyskakování prvků z jednoduché fronty se ve výsledku získá pořadí dat FIFO.
Níže je a jednoduchá implementace prioritní fronty.
Krajta
# 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())> |
Výstup:
12 1 14 7 14 12 7 1
Všimněte si, že časová složitost odstranění je ve výše uvedeném kódu O(n). A lepší implementace je použít Binární halda který se obvykle používá k implementaci prioritní fronty. Všimněte si, že Python poskytuje heapq také v knihovně.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
