Prioritātes rinda Python
Prioritārās rindas ir abstraktas datu struktūras, kur katram rindas datiem/vērtībai ir noteikta prioritāte. Piemēram, aviokompānijās bagāža ar nosaukumu Business vai First Class pienāk agrāk nekā pārējā.
Prioritātes rinda ir rindas paplašinājums ar tālāk norādītajiem rekvizītiem.
- Elements ar augstu prioritāti tiek izslēgts no rindas pirms elementa ar zemu prioritāti.
- Ja diviem elementiem ir vienāda prioritāte, tie tiek apkalpoti atbilstoši to secībai rindā.
Dažādi lietojumprogrammas Prioritātes rindā datorzinātnēs ir:
Darba plānošanas algoritmi, CPU un diska plānošana, dažādu procesu koplietošanas resursu pārvaldība utt.
Galvenās atšķirības starp prioritāro rindu un rindu:
- Rindā vispirms tiek noņemts vecākais elements. Prioritātes rindā elements, kura pamatā ir visaugstākā prioritāte, tiek izslēgts no rindas.
- Kad elementi tiek izlaisti no prioritārās rindas, iegūtais rezultāts tiek sakārtots augošā vai dilstošā secībā. Ja elementi tiek izlikti no vienkāršas rindas, rezultātā tiek iegūta datu FIFO secība.
Zemāk ir a vienkārša īstenošana no prioritārās rindas.
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]>>> :> > myQueue> => PriorityQueue()> > myQueue.insert(> 12> )> > myQueue.insert(> 1> )> > myQueue.insert(> 14> )> > myQueue.insert(> 7> )> > print> (myQueue)> > while> not> myQueue.isEmpty():> > print> (myQueue.delete())> |
Izvade:
12 1 14 7 14 12 7 1
Ņemiet vērā, ka dzēšanas laika sarežģītība iepriekš minētajā kodā ir O(n). A labāka īstenošana ir izmantot Binārā kaudze ko parasti izmanto, lai ieviestu prioritāro rindu. Ņemiet vērā, ka Python nodrošina kaudze q arī bibliotēkā.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
