Prioriteettijono

1. Prioriteettijono tietorakenteena

Prioriteettijono on jono jonka alkioilla on tärkeysjärjestys. Vietäessä alkiota jonoon määritellään alkion tärkeys (tästedes: prioriteetti), ja jonosta poistetaan aina parhaan prioriteetin omaava alkio. Loput tekstistä sitten kunhan sitä saadaan aikaiseksi.

Kirjastossa on määritelty tyyppi PRIORITYTYPE, joka on alustavasti liukulukutyyppiä float.

Aikavaativuuksista nyt (Tapani, Simo) sen verran, että prioriteettijono on nyt toteutettu järjestetyllä puulla, joten aikavaativuudet ovat pahimmillaan O(n). Kuitenkin, toteutin punamustan puun sillä tavalla, että se voidaan suht helposti ottaa käyttöön tässäkin tietorakenteessa, siis saadaan O(log n).

2. Prioriteettijonon operaatiot

PRIQUEUE_CREATE(P, desc);

void PRIQUEUE_CREATE(PRIQUEUE P, DESCRIPTOR desc);

void INT_PRIQUEUE_CREATE(PRIQUEUE P);
void FLOAT_PRIQUEUE_CREATE(PRIQUEUE P);
void CHARP_PRIQUEUE_CREATE(PRIQUEUE P);
void VOIDPTR_PRIQUEUE_CREATE(PRIQUEUE P);

Aikavaativuus : O(1)

PRIQUEUE_INSERT(P, x, pri);

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, char* x, PRIORITYTYPE pri);
void VOIDPTR_PRIQUEUE_INSERT(PRIQUEUE P, void* x, PRIORITYTYPE pri);

Aikavaativuus : O(n)

PRIQUEUE_DELETEMIN(P);

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);

Aikavaativuus : O(n)

PRIQUEUE_MIN(P)

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

Aikavaativuus : O(n)

PRIQUEUE_EMPTY(P);

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);

Aikavaativuus : O(1)

PRIQUEUE_FREE(P);

Jos void*- tai char*-pakassa on talletettuna tietoa jolle on varattu muistia eikä siihen enää päästä käsiksi pakan tuhoamisen jälkeen, täytyy ennen PRIQUEUE_FREE:n kutsumista huolehtia varatun muistitilan vapauttamisesta.

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);

Aikavaativuus : O(n)

Luentomonisteessa mainitsemattomat operaatiot

PRIQUEUE_LESS(P, x, y);

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

Aikavaativuus : yksinkertaisille tyypeille O(1)

PRIQUEUE_SAME(P, x, y);

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

Aikavaativuus : yksinkertaisille tyypeille O(1)

PRIQUEUE_TYPE(P);

DESCRIPTOR PRIQUEUE_TYPE(PRIQUEUE P);

Aikavaativuus : O(1)