Prioriteettijonoille

Prioriteettijono on abstrakti tietotyyppi, jossa jokaisella alkiolla on sille annettu prioriteetti. Operaationa on poimia ja palauttaa alkio, jolla on korkein (tai matalin) prioriteetti. Prioriteettijonot ovat hyödyllisiä tilanteissa, joissa töitä on järjestettävä jonoon prioriteetien mukaan. Usein käytetään minimi- tai maksimi-prioriteettijonoa: min-priority queue palauttaa pienimmän prioriteetin, max-priority queue suurimman.

Yleisimpiä toteutuksia ovat binäärinen heap, d-ary heap ja muut heap-pohjaiset rakenteet. Muita vaihtoehtoja ovat tasapainotetut hakupuut (kuten red-black tree) sekä erikoisrakenteet kuten Fibonacci-heap ja pairing-heap. Aikavaativuudet riippuvat toteutuksesta: insert ja extract-min / extract-max ovat yleisesti O(log n) heapissä; find-min tai find-max on usein O(1). Decrease-key ja increase-key ovat tyypillisesti O(log n); joissain rakenteissa niiden vaikutus voi olla amortisoitua.

Käyttökohteita ovat esimerkiksi lyhyimmän polun etsinnän algoritmit (esim. Dijkstra), Huffman-koodaus, tapahtumien simulointi sekä tehtävien aikataulutus ja resurssienhallinta, joissa prioriteetit voivat muuttua dynaamisesti.

Suoritusympäristöissä useat ohjelmointikielet tarjoavat valmiita toteutuksia: C++ std::priority_queue, Java PriorityQueue ja Pythonin heapq-moduuli. Valinta riippuu tarvittavista operaatiosta ja aikavaatimuksista sekä siitä, tuetaanko käytetyssä rakenteessa decrease-key-operaatio. Prioriteettijono ei välttämättä ole stabiili; vakaus riippuu toteutuksesta.