„Python“ prioritetinė eilė
Prioritetinės eilės yra abstrakčios duomenų struktūros, kuriose kiekvienas eilės duomenims/reikšmei suteikiamas tam tikras prioritetas. Pavyzdžiui, oro linijose bagažas, pavadintas Verslo arba Pirmos klasės, atkeliauja anksčiau nei kiti.
Prioritetinė eilė yra eilės plėtinys su šiomis savybėmis.
- Aukšto prioriteto elementas ištraukiamas prieš elementą, kurio prioritetas žemas.
- Jei du elementai turi tą patį prioritetą, jie pateikiami pagal eilę.
Įvairūs programos Informatikos prioritetų eilės yra:
Darbo planavimo algoritmai, procesoriaus ir disko planavimas, įvairių procesų bendrinamų išteklių valdymas ir kt.
Pagrindiniai prioritetų eilės ir eilės skirtumai:
- Eilėje pirmiausia pašalinamas seniausias elementas. Prioritetinėje eilėje elementas, pagrįstas aukščiausiu prioritetu, ištraukiamas iš eilės.
- Kai elementai iškeliami iš prioritetinės eilės, gautas rezultatas rūšiuojamas didėjančia arba mažėjimo tvarka. Kai elementai iškeliami iš paprastos eilės, rezultate gaunama FIFO duomenų tvarka.
Žemiau yra a paprastas įgyvendinimas prioritetinės eilės.
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())> |
Išvestis:
12 1 14 7 14 12 7 1
Atkreipkite dėmesį, kad ištrynimo sudėtingumas aukščiau pateiktame kode yra O (n). A geresnis įgyvendinimas yra naudoti Dvejetainė krūva kuris paprastai naudojamas prioritetinei eilei įgyvendinti. Atminkite, kad Python suteikia heapq bibliotekoje taip pat.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
