Prioriteettijono (ohjelmointi)

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 25. maaliskuuta 2021 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Prioriteettijono on ohjelmoinnin abstrakti tietotyyppi , joka tukee kahta pakollista toimintoa -  lisää elementti ja poimi maksimi [1] (minimi). Oletetaan, että jokaiselle elementille on mahdollista laskea sen prioriteetti  - reaaliluku tai yleisessä tapauksessa lineaarisesti järjestetyn joukon alkio [2] .

Kuvaus

Tärkeimmät prioriteettijonon toteuttamat menetelmät ovat seuraavat [2] [3] [1] :

Tässä tapauksessa pienempi avainarvo vastaa korkeampaa prioriteettia.

Joissakin tapauksissa on luonnollisempaa, että avain kasvaa prioriteetin mukana. Sitten toista menetelmää voidaan kutsua extract_maximum()[1] .

On olemassa useita toteutuksia, joissa molemmat perustoiminnot suoritetaan pahimmassa tapauksessa rajoitetun ajan (katso "O" suuri ja "o" pieni ), missä  on tallennettujen parien määrä.

Esimerkkejä

Esimerkkinä prioriteettijonosta harkitse työntekijän tehtäväluetteloa. Kun hän suorittaa yhden tehtävän, hän siirtyy seuraavaan - korkeimpaan prioriteettiin (avain on prioriteetin käänteisluku) - eli hän suorittaa maksimin poimimisen. Pomo lisää tehtäviä luetteloon ilmoittamalla niiden prioriteetin, eli suorittaa elementin lisäämisen.

Prioriteettijonon laajennukset

Käytännössä prioriteettijonoliitäntää laajennetaan usein muilla toiminnoilla [4] [3] :

Indeksoiduissa prioriteettijonoissa (osoite [5] ) on mahdollista käyttää elementtejä indeksin mukaan. Tällaisia ​​jonoja voidaan käyttää esimerkiksi useiden lajiteltujen sekvenssien yhdistämiseen (multiway merge) [1] .

Myös kaksipäistä prioriteettijonoa (DEPQ ) voidaan harkita ,  jossa on pääsyoperaatioita sekä minimi- että maksimielementtiin [6] .

Toteutukset

Prioriteettijono voidaan toteuttaa eri tietorakenteiden perusteella.

Yksinkertaisimmat (ja ei kovin tehokkaat) toteutukset voivat käyttää järjestämätöntä tai järjestettyä taulukkoa , linkitettyä listaa , joka sopii pieniin jonoihin. Tässä tapauksessa laskelmat voivat olla joko "laiskoja" (laskelmien vakavuus siirtyy elementin poistamiseen) ja varhaisia ​​(innokkaita), kun elementin lisääminen on vaikeampaa kuin sen poistaminen. Toisin sanoen yksi operaatioista voidaan suorittaa ajoissa ja toinen - pahimmassa tapauksessa , missä  on jonon pituus [1] .

Tehokkaampia ovat kasapohjaiset toteutukset , joissa molemmat toiminnot voidaan suorittaa pahimmassa tapauksessa ajallaan [1] . Näitä ovat binäärikeko , binomikasa , fibonacci - kasa , parituskeko[6] .

Prioriteettijonon abstrakti tietotyyppi (ATD) johdetaan keon ADT:stä nimeämällä vastaavat funktiot uudelleen. Minimi (maksimi) arvo on aina kasan yläosassa [7] .

Python-esimerkki

Python-standardikirjasto sisältää moduulin heapq[8] , joka toteuttaa prioriteettijonon [9] :

# tuo kaksi jonofunktiota tässä artikkelissa käytetyillä nimillä kohdasta heapq import heappush as insert , heappop muodossa extract_maximum pq = [] # alusta listan lisäys ( pq , ( 4 , 0 , "p" )) # lisää elementti "p" jonoon " indeksillä 0 ja prioriteetilla 4 insert ( pq , ( 2 , 1 , "e" )) insert ( pq , ( 3 , 2 , "a" )) insert ( pq , ( 1 , 3 , "h") ) ) _tärkeysjärjestyksessänousevassaelementtiäneljätulosta# _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

Tämä esimerkki tulostaa sanan "kasa".

Muistiinpanot

  1. ↑ 1 2 3 4 5 6 Sedgewick, Wayne, 2011 .
  2. ↑ 1 2 Aho, Hopcroft, Ullman, 2000 .
  3. ↑ 1 2 Kormen et al., 2005 .
  4. ↑ Robert Sedgewick. Algoritmit C++:ssa, osat 1–4: perusteet, tietorakenne, lajittelu, haku. – Kolmas painos. - Addison-Wesley Professional. — 752 s. - ISBN 978-0-7686-8533-6 .
  5. ↑ Mehlhorn, Sanders, 2008 .
  6. ↑ 1 2 Sahni, Mehta, 2018 .
  7. ↑ Rabhi, Lapalme, 1999 .
  8. ↑ 8.4. heapq - Keon jonoalgoritmi . Haettu 25. marraskuuta 2014. Arkistoitu alkuperäisestä 4. joulukuuta 2017.
  9. ↑ David Beazley, Brian K. Jones. 1.5. Prioriteettijonon käyttöönotto // Python-keittokirja. - 3. painos. - O'Reilly Media, Inc., 2013. - 706 s. — ISBN 978-1-4493-4037-7 .

Kirjallisuus

  • Kormen, T., Leizerson, C., Rivest, R., Stein, K. Algoritmit: rakentaminen ja analyysi = Introduction to Algorithms / Ed. I. V. Krasikova. - 2. painos - M. : Williams , 2005. - 1296 s. — ISBN 5-8459-0857-4 .
  • Aho A. W., Hopcroft J. E., Ullman J. D. Data Structures and Algorithms. - Williams, 2000. - 384 s. — ISBN 9785845901224 . , 4.10. Prioriteettijonot
  • Robert Sedgewick; Kevin Wayne. 2.4 Prioriteettijonot // Algoritmit. – Neljäs painos. - Addison-Wesley Professional, 2011. - 992 s. — ISBN 978-0-13-276257-1 .
  • Gerth Stølting Brodal, Chris Okasaki. Optimaaliset puhtaasti toiminnalliset prioriteettijonot  // BRICS-raporttisarja. - Tietojenkäsittelytieteen laitos Århusin yliopisto, 1996. - No. RS-96-37 . — ISSN 0909-0878 .
  • Fethi Rabhi ja Lapalme, G. Algoritmit: Toiminnallinen ohjelmointimenetelmä . - Addison-Wesley, 1999. - P.  92-93 , 106-107. - 235 p. — ISBN 9780201596045 .
  • Sartaj Sahni ja Dinesh P. Mehta. Osa II: Priority Queues // Tietorakenteiden ja sovellusten käsikirja. – 2. painos - Chapman ja Hall / CRC, 2018. - 1100 s. — ISBN 9781498701853 .
  • Mehlhorn, Kurt, Sanders, Peter. 6. Prioriteettijonot // Algoritmit ja tietorakenteet: Perustyökalut. - Springer, 2008. - 300 s. — ISBN 978-3-540-77978-0 .

Linkit