Prioriteettijono

Sisältö:

Määritelmä

Prioriteettijono on muuten kuin tavallinen jono,  mutta siihen laitetut alkiot voi poistaa jonosta ainoastaan tärkeysjärjestyksessä, joka määräytyy alkioiden prioriteetin (eli tärkeysjärjestystä kuvaavan lukuarvon) perusteella. Jokaiselle prioriteettijonoon lisättävälle alkiolle on lisäysoperaatiota käytettäessä annettava samalla prioriteetti liukulukumuotoisena lukuna. (Esimerkiksi 3.12, 2.3 ja 3.4 ovat eri suuruisia prioriteetin arvoja.) Kun prioriteettijonosta sitten poistetaan alkio poisto-operaatiolla, poistuu jonosta se alkio, jolla on pienin prioriteetin arvo. Jos prioriteettijonossa on useita sellaisia alkioita, joilla on keskenään sama prioriteetti, nämä poistuvat jonosta siinä järjestyksessä kuin ne tavallisessa jonossa poistuisivat: ensimmäisenä jonoon laitettu alkio myös poistuu ensimmäisenä kaikista saman prioriteetin omaavista alkioista. Jos kaikkien prioriteettijonoon lisättävien alkioiden prioriteetti pidetään aina samana, prioriteettijono käyttäytyy kuten tavallinen jono.



Käytettävistä tyypeistä ja funktioiden nimeämisestä

Prioriteettijono voidaan luoda tallettamaan yleisiä ELEMENT-tyypin alkioita tai erikseen kokonaisluku-, reaaliluku-, merkki- tai osoitintyyppisiä alkioita. (Ks. tarkemmat tietotyyppien kuvaukset luvusta Tietotyypit.)

Silloin, kun halutaan (tai on tarkoituksenmukaista) käyttää yleistä alkiotyyppiä ELEMENT, prioriteettijonoon liittyvien funktioiden nimet alkavat PRIQUEUE_ -etuliitteellä, mutta jos prioriteettijonon alkioiden tyyppi määrätään erikseen, funktioiden nimien eteen tulee lisäksi käsiteltävän prioriteettijonon alkiotyypin tunnus, joka voi olla INT_, FLOAT_, CHARP_ tai VOIDPTR_. (Kokonaisluku-, reaaliluku-, merkki- tai osoitintyyppi) Näin saadaan tiettyä tietotyyppiä käsittelevien prioriteettijonon funktioiden nimien alkuosaksi seuraavat:

Yleisessä prioriteettijonossa:
Vastaavat lyhenteet nimille ovat:

Yllä olevat nimen alkuosat ovat siis etuliitteitä varsinaisen funktion nimen edessä: ' ...' korvataan seuraavassa kohdassa esitellyillä funktioiden nimillä, esimerkiksi INT_PRIQUEUE_CREATE tai lyhennettynä IPQ_CREATE. Lyhenteitä voi käyttää aina niin halutessaan.



Prioriteettijonon funktiot

 Muutama huomio funktioiden käytöstä

Kun luodaan yleinen prioriteettijono, kutsutaan funktiota PRIQUEUE_CREATE parametreilla P ja D, joista P on luotavan prioriteettijonon nimi ja D luotavan jonon tyyppi. Jonon tyyppiä kutsutaan yleisen jonon tapauksessa kuvaajaksi (DESCRIPTOR). Ks. tarkempia tietoja DESCRIPTOR-parametrista luvusta Tietotyypit.

Jos luodaan tietyn tyyppisiä alkioita sisältävä prioriteettijono, välitetään PRIQUEUE_CREATE -funktiolle parametrina pelkästään luotavan jonon nimi P. Tällöin on käytettävä oikeaa alkiotyyppiä vastaavaa funktion nimeä, esimerkiksi kokonaislukujen prioriteettijonoa luotaessa on käytettävä funktiota INT_PRIQUEUE_CREATE. (IPQ_CREATE)

PRIQUEUE_INSERT -funktiossa parametri pri tarkoittaa prioriteettia. Se on määritelty tietorakennekirjastossa tyypiksi float, ja näin ollen prioriteetin arvon täytyy aina olla liukuluku.

Prioriteettijonon funktioiden esittelyt (C-kieleen)


Uuden prioriteettijonon luominen:
PRIQUEUE_CREATE (P, D)

Yleinen PRIQUEUE_CREATE(P, D) muodostaa tyhjän prioriteettijonon P, ja asettaa sen kuvaajaksi kuvaajan D = {INT_DESC| FLOAT_DESC| CHARP_DESC| VOIDPTR_DESC}. Mikäli prioriteettijono P ei ole tyhjä prioriteettijono, kaikki prioriteettijonossa ollut tieto menetetään, ja se jää varamaan muistia turhaan. Tyypitetyt operaatiot muodostavat omaa tyyppiään olevan prioriteettijonon P.
Aikavaativuus : O(1)

void PRIQUEUE_CREATE (PRIQUEUE P, DESCRIPTOR D);
void INT_PRIQUEUE_CREATE(PRIQUEUE P);
void FLOAT_PRIQUEUE_CREATE(PRIQUEUE P);
void CHARP_PRIQUEUE_CREATE(PRIQUEUE P);
void VOIDPTR_PRIQUEUE_CREATE(PRIQUEUE P);

Alkion lisääminen:
PRIQUEUE_INSERT(P,x,pri)

Lisää alkion x prioriteettijonoon P asettaen sille prioriteetin pri. Tyypitetyt operaatiot vievät prioriteettijonoon omaa tyyppiään olevan alkion. 
Aikavaativuus : O(n) 

void PRIQUEUE_INSERT (PRIQUEUE P, ELEMENT X, PRIORITYTYPE pri);
void INT_PRIQUEUE_INSERT (PRIQUEUE P, INT_TYPE x, PRIORITYTYPE pri);
void FLOAT_PRIQUEUE_INSERT (PRIQUEUE P, FLOAT_TYPE x, PRIORITYTYPE pri);
void CHARP_PRIQUEUE_INSERT (PRIQUEUE P, CHARP_TYPE x, PRIORITYTYPE pri);
void VOIDPTR_PRIQUEUE_INSERT (PRIQUEUE P, *void x, PRIORITYTYPE pri);

Alkion poistaminen:
PRIQUEUE_DELETEMIN (P)

Poistaa prioriteettijonosta P pieniprioriteettisimman alkion. 
Aikavaativuus : O(n)

void PRIQUEUE_DELETEMIN (PRIQUEUE P);
void INT_PRIQUEUE_DELETEMIN (PRIQUEUE P);
void FLOAT_PRIQUEUE_DELETEMIN (PRIQUEUE P);
void CHARP_PRIQUEUE_DELETEMIN (PRIQUEUE P);
void VOIDPTR_PRIQUEUE_DELETEMIN (PRIQUEUE P);

Alkion hakeminen:
PRIQUEUE_MIN(P)

Palauttaa prioriteettijonon P prioriteetiltään pienimmän alkion arvon.     
Aikavaativuus : O(n)

ELEMENT PRIQUEUE_MIN (PRIQUEUE P);
INT_TYPE INT_PRIQUEUE_MIN (PRIQUEUE P);
FLOAT_TYPE FLOAT_PRIQUEUE_MIN (PRIQUEUE P);
CHARP_TYPE CHARP_PRIQUEUE_MIN (PRIQUEUE P);
*void VOIDPTR_PRIQUEUE_MIN (PRIQUEUE P);

Prioriteettijonon varaaman tilan vapauttaminen:
PRIQUEUE_FREE (P)

Vapauttaa kaiken prioriteettijonon P varaaman tilan ja asettaa prioriteettijonon P määrittelemättömäksi prioriteettijonoksi. On hyvä ohjelmointitapa vapauttaa ohjelman lopussa ohjelman varaama tila. Jos void*- tai char*-prioriteettijonossa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi jonon tuhoamisen jälkeen, täytyy ennen PRIQUEUE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta. 
Aikavaativuus : O(n)

void PRIQUEUE_FREE (PRIQUEUE P);
void INT_PRIQUEUE_FREE (PRIQUEUE P);
void FLOAT_PRIQUEUE_FREE (PRIQUEUE P);
void CHARP_PRIQUEUE_FREE (PRIQUEUE P);
void VOIDPTR_PRIQUEUE_FREE(PRIQUEUE P);

Prioriteettijonon tyypin tarkistaminen:
PRIQUEUE_TYPE (P)

Palauttaa prioriteettijonon P kuvaajan. Käytetään lähinnä tilanteessa, jossa ei ohjelmoitaessa tiedetä minkätyyppinen prioriteettijono joudutaan luomaan. Uusi prioriteettijono Q, joka on samaa tyyppiä kuin prioriteettijono P luodaan komennolla PRIQUEUE_CREATE(Q, PRIQUEUE_TYPE(P));.
Aikavaativuus : O(1)

DESCRIPTOR PRIQUEUE_TYPE (PRIQUEUE P);

Alkioiden vertailu:
PRIQUEUE_LESS (P, x, y)
PRIQUEUE_SAME (P, x, y)

Palauttavat tiedon siitä ovatko prioriteettijonon P määräämää tyyppiä olevat elementit x ja y samoja (SAME), tai onko x järjestyksessä ennen y:tä (LESS). Elementtien x ja y pitää olla samaa tyyppiä kuin prioriteettijonon P alkiot (muttei niiden ole pakko olla jonon P alkioita). Jos x=y, niin PRIQUEUE_SAME palauttaa siis TRUE (!=0), ja jos x<y niin PRIQUEUE_LESS palauttaa TRUE (!=0). Merkkijonojonossa vertaillaan merkkijonojen välistä aakkosjärjestystä.
Aikavaativuus : yksinkertaisille tyypeille O(1)

int PRIQUEUE_LESS (PRIQUEUE P, ELEMENT x, ELEMENT y);
int PRIQUEUE_SAME (PRIQUEUE P, ELEMENT x, ELEMENT y);

Prioriteettijonon tyhjyyden tarkistus:
PRIQUEUE_EMPTY (P)

Palauttaa tiedon siitä onko prioriteettijono P tyhjä prioriteettijono. C-kielessä palautusarvo on !=0, jos prioriteettijono on tyhjä, ja 0 mikäli prioriteettijono ei ole tyhjä.
Aikavaativuus : O(1)

int PRIQUEUE_EMPTY (PRIQUEUE P);
int INT_PRIQUEUE_EMPTY (PRIQUEUE P);
int FLOAT_PRIQUEUE_EMPTY (PRIQUEUE P);
int CHARP_PRIQUEUE_EMPTY (PRIQUEUE P);
int VOIDPTR_PRIQUEUE_EMPTY(PRIQUEUE P);