Prioritetni red

Prioritetni red je apstraktna struktura. To znači da u ovom trenutku još ne govorimo o implementaciji.
Prioritetni red mora imati zadovoljene tri operacije, to su: ubacivanje, brisanje i upit. (engl. push, pop, top)
U strukturu se ubacuju elementi, iz strukture se briše najbolji element i upitom se dobija najbolji element (npr. maksimum, minimum,... - ovisno o operatoru usporedbe).

Važno pitanje koje trebamo postaviti prije korištenja bilo kakve strukture podataka je: Koliko vremena je dopušteno potrošiti na neku operaciju koja se obavlja nad strukturom.

Ovo pitanje je veoma važno jer određuje implementaciju. Ako je odgovor na pitanje: češće ubacivanje, implementacija je veoma jednostavna - koristi se običan niz, a vrijednost upita određuju se prolaskom kroz sve elemente, tj. vremenska složenost je . Ista vremenska složenost je za izbacivanje elementa. Vremenska složenost ubacivanja je naravno .

( - broj ubacivanja, - broj upita, - ukupan broj elemenata ubačenih u strukturu)

Najčešće su i približno jednaki (tj. rijetko kada se koristi gornje opisana implementacija). Prva ideja koja je na tragu prve implementacije - niz čuvamo uvijek sortiranim (ubacimo element na pravu poziciju). Za upit i brisanje znamo koji je najbolji element u vremenu (to je prvi element u nizu). Samo sada smo pogoršali vrijeme ubacivanje - .

Postoji li struktura na razini implementacije koja bi poboljšala vrijeme ubacivanja? Da, postoji i zove se Heap. Kako ništa nije besplatno tako i postizanje boljeg vremena ubacivanja uzrokovati će veću složenost izbacivanja (sada će umjesto biti ).

Heap

Kada govorimo o heapu najčešće mislimo na strukturu koja u sebi sadrži binarno stablo (više o tome kasnije). Ali postoje i drugi načini organizacije heap-a.

Vremenske složenosti za operaciju ubacivanja, brisanja, upita su redom: , , .

Ideja

Nad potpunim binarnim stablom, u kojem je roditelj uvijek bolji od svoje djece, konstruirat ćemo operacije za ubacivanje, izbacivanje i upit.

Binarno stablo biti će predstavljeno nizom indeksiranim od 1. Djeca nekog čvora koji je u nizu zapisan na indeksu , nalaze se na indeksima i na . Ovakva organizacija indeksa nam omogućuje jednostavnu i brzu implementaciju potpunog binarnog stabla (osim ove implementacije stabla mogu se koristiti i druge implementacije kao što je implementacija stabla pomoću pokazivača).

Primjer implementacije potpunog binarnog stabla pomoću niza:

Prikaz stabla u nizu (indeksiranom od 1):

Ubacivanje

Ubacivanje se obavlja tako da se novi element doda na novi indeks u nizu (prvi koji nije zauzet). Zatim se taj element penje prema vrhu stabla tako da u svakom koraku mora biti zadovoljeno svojstvo da je roditelj bolji od elementa (djeteta). Kada je to zadovoljeno više se ne penjemo.

Pretpostavimo da u nekom trenutku imamo heap koji izgleda ovako (kao rezultat upita ovaj heap daje najveći broj):

Ubacit ćemo 16 u heap. Broj ubacujemo na prvo slobodno mjesto:

Gledamo da li je roditelj manji od djeteta. Ako je, zamijenimo ih:

Penjemo se tako prema vrhu sve dok ne zadovoljimo svojstvno heap-a. Konačno imamo:

Izbacivanje

Izbacivanje radimo tako da zadnji element u nizu stavimo kao čvor stabla. Zatim se spuštamo po stablu tako dugo dok element nije bolji od oba djeteta. Ako su oba djeteta bolja, idemo u onu granu gdje je bilo bolje od ta dva djeteta (zamijenjujemo s boljim djetetom). Ovo je veoma važno jer kad bi išli u granu drugog djeteta pokvarili bi svojstvo stabla.

Želimo izbaciti najveći broj. Zamijenimo korijen čvora s čvorom koji se nalazi najdublje i najdesnije u stablu. To je čvor koji u sebi ima broj 8:

Sad se korijen stabla spušta. Potrebno je zadovoljiti svojstvo stabla da je roditelj veći (ili jednak) od svoje djece. U prvom koraku oba djeteta su veća od promatranog čvora (8). Zamijenjujemo s onim djetetom koje je veće (provjerite da bi u drugom slučaju narušili svojstvo stabla).

Konačan izgled stabla postiže se kada je promatrani čvor veći (ili jednak) od oba djeteta:

Upit

Obavljanje upita je veoma jednostavno. Uzmemo element koji se nalazi na indeksu 1, tj. korijen stabla.

Implementacija

U ovom primjeru koda pretpostavljamo da imamo definirane slijedeće varijable:

const int MAXI = 1000001;
const int ERROR = 0x7fffffff;

int heap[MAXI] = {0};
int heapEnd = 1; //indeks prvog elementa u heapu koji nije popunjen

Ubacivanje

void push(int x)
{
  heap[heapEnd] = x;  
  for(int i = heapEnd ; i > 1 ; )
  {
    if ( heap[i] > heap[i/2] )
    { 
      swap(heap[i], heap[i/2]); 
      i /= 2;
    }
    else
      break;    
  }
  heapEnd += 1;
}

Izbacivanje

void pop()
{
  if (heapEnd == 1) 
    return; 
  heapEnd -= 1;
  heap[1] = heap[heapEnd];
  for(int i = 1; ; )
  {
    if ( 2*i >= heapEnd ) break;
    if ( 2*i+1 < heapEnd && heap[i] < heap[2*i+1] && heap[2*i] < heap[2*i+1] )
    {
      swap(heap[i], heap[2*i+1]);
      i = 2*i +1;
    } 
    else if ( heap[i] < heap[2*i] )
    {
      swap(heap[i], heap[2*i]);
      i = 2*i; 
    }
    else
      break;
  }
}

Upit

int top()
{
  if ( heapEnd == 1 ) return ERROR;
  return heap[1];
}

Gotova implementacija

Preporuča se korištenje gotovih implementacija prioritetnog reda (ako je za rješavanje problema potrebna baš takva struktura bez većih modifikacija).
Popis gotovih struktura u nekim od programskih jezika:

• C++/STL: priority_queue<E>
• Java: java.util.PriorityQueue<E>

Zadaci

• Postoji čarobna kutija u koju se ubacuju brojevi (pozitivni < ). Kutija je čarobna zato što sadrži k najmanjih brojeva koji su do tada ubačeni u nju (ili manje od k ako je ubačeno manje od k brojeva). Sve ostale brojeve "pojede". Na ulaz se dovode dvije vrste naredbi: POSTAVI x i UZMI. POSTAVI x označava da se u kutiju ubacuje broj x. UZMI označava da se iz kutije uzima najveći od opisanih k brojeva koje kutija nije pojela. Potrebno je odrediti k najmanjih brojeva koji se nalaze u kutiji nakon izvršavanja svih naredbi. Pretpostavlja se da ima jako puno ovakvih naredbi i k je relativno velik broj (~ ) tj. jednostavna implementacija pomoću pretraživanja niza nije dopuštena.

© Dino Šantl, 2013.

Ovaj članak objavljen je pod
Creative Commons Attribution-ShareAlike 3.0 Croatia License