Priority Queue Pythonissa
Prioriteettijonot ovat abstrakteja tietorakenteita, joissa jokaisella jonon tiedolla/arvolla on tietty prioriteetti. Esimerkiksi lentoyhtiöillä matkatavarat, joiden otsikko on Business tai First Class, saapuvat aikaisemmin kuin muut.
Priority Queue on jonon laajennus seuraavilla ominaisuuksilla.
- Korkean prioriteetin elementti poistetaan jonosta ennen matalan prioriteetin elementtiä.
- Jos kahdella elementillä on sama prioriteetti, ne toimitetaan niiden järjestyksen mukaan jonossa.
Eri sovellukset Tietojenkäsittelytieteen Priority-jonosta ovat:
Työn ajoitusalgoritmit, suorittimen ja levyn ajoitus, eri prosessien kesken jaettujen resurssien hallinta jne.
Tärkeimmät erot prioriteettijonon ja jonon välillä:
- Queue-kohdassa vanhin elementti poistetaan jonosta ensin. Kun Priority Queue -tilassa korkeimpaan prioriteettiin perustuva elementti poistetaan jonosta.
- Kun elementit ponnataan pois prioriteettijonosta, saatu tulos lajitellaan joko kasvavaan tai laskevaan järjestykseen. Kun elementtejä pompataan yksinkertaisesta jonosta, tulokseen saadaan FIFO-tietojen järjestys.
Alla on a yksinkertainen toteutus prioriteettijonosta.
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())> |
Lähtö:
12 1 14 7 14 12 7 1
Huomaa, että poistamisen aikamonimutkaisuus on O(n) yllä olevassa koodissa. A parempi toteutus on käyttää Binäärikeko jota tyypillisesti käytetään prioriteettijonon toteuttamiseen. Huomaa, että Python tarjoaa kasaq myös kirjastossa.
Time complexity: By using heap data structure to implement Priority Queues Insert Operation: O(log(n)) Delete Operation: O(log(n))
