Prioriteettijono

Prioriteettijono (engl. priority queue) on tietojenkäsittelytieteessä abstrakti tietotyyppi, joka säilöö alkioita ja niihin sisällytettyjä prioriteetteja. Tyypillinen käyttötapaus voisi olla vaikkapa käyttöjärjestelmän prosessien hallinta, jossa tärkeimmät prosessit saavat eniten suoritinaikaa. Prioriteettijonosta on kaksi symmetristä versiota: minimiprioriteettijono tukee pienimmän ja maksimiprioriteettijono suurimman prioriteetin omaavan alkion poimimista. Tyypillinen rajapinta on seuraava:

  • insert(x): lisää alkion x prioriteettijonoon
  • minimum/maximum: palauttaa alkion, jolla on pienin/suurin prioriteetti
  • extract min/max: poistaa ja palauttaa alkion, jolla on suurin prioriteetti (vrt. pinon pop)
  • decrease/increase key(x, k): laskee/korottaa alkion x prioriteettia arvoon k, joka on yhtä suuri tai pienempi/suurempi kuin x:n nykyinen prioriteetti

Toteutus

[muokkaa | muokkaa wikitekstiä]

Tyypillinen toteutus prioriteettijonolle on keko, jolla kaikki prioriteettijonon operaatiot onnistuvat vähintäänkin asymptoottisessa suoritusajassa log(n).

Lähteet

[muokkaa | muokkaa wikitekstiä]
  • Cormen, Thomas & Leiserson, Charles & Rivest, Ronald & Stein, Clifford: ”Chapter 6: Heapsort”, Introduction to Algorithms – 2nd ed. s. 127–140. MIT Press ja McGraw-Hill, 2001. ISBN 0-262-03293-7