Vrsta s prednostjo je abstraktna podatkovna struktura (APS).

V njen so elementi urejeni po prednosti oz. prioriteti.

Za vrsto s prednostjo ne velja pravilo FIFO (first in first out).

S pomočjo te podatkovne strukture urejamo polje elementov.

PRIMER:

Torej ima večjo prioriteto tisti, ki je prej prišel v čakalnico.

Ustvari ustvari novo prazno vrsto s prednostjo

Vstavi vstavi element s prioriteto v vrsto

Odstrani odstrani element z največjo prioriteto

Največji element vrne največji element oz. element z največjo prioriteto

Vrsto s prednostjo lahko predstavimo na več načinov.

Predstavimo jo lahko kot tabelo, kopico, binomsko kopico, 2-3 drevo in seznam.

V nadaljevanju si bomo podrobnejše ogledali predstavitev s kopico in tabelo.

Poznamo dve vrsti tabel: urejeno in neurejeno

V neurejeni tabeli so dodani elementi po naključju.

Ti dve predstavitvi se razlikujeta po časovni zahtevnosti (vračanje elementa z najvišjo prioriteto in vstavljanje elementa).

Če želimo poiskati element z največjo prioriteto je način z urejeno tabelo enostavnejši.

Podatke v tabeli urejamo naraščajoče ali padajoče. Pri predstavitvi vrste s prednostjo je bolj smiselno, da so podatki urejeni naraščajoče.

Taka predstavitev je primerna, če v vrsto s prednostjo ne vstavljamo veliko podatkov. Saj nam taka predstavitev vzame veliko več časa kot katerakoli druga.

Pri tej predstavitvi je vstavljanje elementov bolj enostavno kot operaciji za vračanje največjega in odstranjevanje elementa.

Operacije pri predstavitvi vrste s prednostjo s pomočjo neurejene tabele imajo naslednje časovne zahtevnosti:

• Ustvari Ustvari novo prazno vrsto s prednostjo.
• Vstavi ima časovno zahtevnost O(1) Pri tej predstavitvi je ta operacija enostavnejša kot pri urejeni tabeli. Element samo vstavimo na prvo prosto mesto v tabeli in kazalec povečamo za 1.
• Največji element ima časovno zahtevnost O(n) Pri tej operaciji moramo primerjati med seboj vse prioritete elementov. Najprej vzamemo tistega na mestu z indeksom 0 in ga primerjamo z naslednjim elementom. Če ima trenutni element večjo prioriteto kot tisti na mestu z indeksom 0, si ga zapomnimo. Drugače pogledamo element, ki mu sledi. Ko pregledamo vse elemente v neurejeni tabeli, vrnemo tistega z najvišjo prednostjo.
• Odstrani ima časovno zahtevnost O(n) Postopek pri tej operaciji je podoben kot pri operaciji vstavi. Pregledamo celotno tabelo in ko najdemo element z največjo prioriteto, ga odstranimo iz tabele. Na njegovo mesto pa postavimo element, ki se trenutno nahaja na zadnjem mestu v tabeli. Kazalec zmanjšamo za 1.

Operacije pri predstavitvi vrste s prednostjo s pomočjo urejene tabele imajo naslednje časovne zahtevnosti:

• Ustvari Ustvari novo prazno vrsto s prednostjo in kazalec postavi na vrednost 0.
• Vstavi ima časovno zahtevnost O(n) Element vstavimo na prvo prosto mesto v tabeli. Pri vstavljanju elementov moramo paziti, da so elementi z večjo prioriteto od vstavljenega za eno mesto bolj desno. Torej element prestavimo iz zadnjega mesta tabele na tisti mesto v tabeli, da so prioritete elementov urejene po velikosti. Kazalec povečamo za 1.
• Največji element ima časovno zahtevnost O(1) Element z najvišjo prioriteto leži na zadnjem mestu v urejeni tabeli. Zato ga samo izpišemo.
• Odstrani ima časovno zahtevnost O(1) Element z najvišjo prioriteto (na zadnjem mestu) odstranimo iz tabele in kazalec zmanjšamo za 1.

Podano imamo vrsto s prednostjo z elementi 2,10,33,46,78 in 96. Prioriteta elementa je enaka njegovi vrednosti. V vrsto zaporedoma vstavimo elementa 2000 in 15. Vrnemo največji element iz tabele in ga nato še odstranimo

Takoj oprazimo, da ima v podani vrsti s prednostjo element 96 največjo prioriteto.

Kazalec=6 mesto na indeksu 6 je prvo prosto mesto v tabeli

Najprej vstavimo v tabelo element z vrednostjo 2000. Vstavimo ga na prvo prosto mesto v tabelo (indeks 6).

Ta element primerjamo s elementom pred njim (na indeksu 5). Ker je 2000>96 pustimo element 2000 na mestu, kjer smo ga vstavili. Kazalec povečamo za ena

Kazalec=7

V tabelo vstavimo še element 15 (na mesto z indeksom 7).

Element 15 primerjamo z največjim elementom v tabeli (z elementom 2000). Ker je 15<2000, zamenjamo njuni mesti.

Spet primerjamo element 15 s sosedom pred njim. Ker je 15<96 zamenjamo njuni mesti. Postopek ponavljamo dokler ni element 15 večji od levega soseda. Dobimo tabelo:

Ko se postopek ustavi, so elementi urejeni po prioriteti naraščajoče. Kazalec povečamo za 1.

Kazalec=8

Dobili smo vrsto s prednostjo.

Sedaj želimo izpisati element z največjo prioriteto. To je torej element, ki stoji zadnji v tabeli. Njegovo mesto je ravno kazalec-1. Torej je element na sedmem mestu v tabeli. Izpišemo ta element. Pri tem se naša tabela ne spremeni.

Navodilo naloge pa zahteva, da še odstranimo element z najvišjo prioriteto. Odstranimo element, ki se nahaja na zadnjem mestu v tabeli in kazalec zmanjšamo za 1.

kazalec=7

Element z vrednostjo 2000 ni več element v vrsti s prednostjo.

Kopica je dvojiško drevo, ki je levo zapolnjeno. Levo zapolnjeno pomeni, da ne moremo začeti zapolnjevati nekega sloja, če prejšnji še ni izpoljnen. Zapolnjujemo torej od leve proti desni.

Predstavitev s kopico je bolj učinkovita kot seznam ali tabela.

Poznamo dve vrsti kopic. minimalna ali maksimalna. Pri maksimalni kopici so elementi urejeni padajoče. Največji element je v korenu drevesa oz. vsak oče je večji ali enak svojima dvema sinovoma. V minimalni kopici pa so elementi urejeni naraščajoče.

Pri predstavitvi vrste s prednostjo s pomočjo kopice ponavadi uporabljamo maksimalno kopico. Elemente razvrščamo po prioriteti od največjo do najmanjše.

Tudi kopico najlaže predstavimo s tabelo. V tem primeru prvo mesto v tabeli (z indeksom 0) izpustimo.

Oče je na mestu i Sinova sta na mestih 2*i in 2*i+1

Lahko povemo tudi obratno Sin je na j-tem mestu Oče je na mestu j/2 upoštevamo celoštevilko deljenje

Kopica kot drevo

Operacije pri predstavitvi vrste s prednostjo s pomočjo kopice imajo naslednje časovne zahtevnosti:

• Ustvari Ustvari novo prazno vrsto s prednostjo.
• Vstavi ima časovno zahtevnost O(logn) Pri operaciji vstavi, element najprej vstavimo v na prvo prosto mesto. Nato drevo (tabelo) preuredimo tako, da bo predstavljalo kopico. To pomeni, da mora biti vsak oče večji ali enak svojem sinu. Kazalec povečamo za 1. Na vsakem sloju v drevesu imamo še enkrat več elementov kot v prejšnjem sloju.
• Največji element ima časovno zahtevnost O(1) Ta operacija je pri predstavitvi s kopico zelo enostavna. Naša naloga je, da samo vrnemo element, ki se nahaja v korenu kopice oz. na prvem mestu v tabeli.
• Odstrani ima časovno zahtevnost O(logn) Kot že vemo, je element z najvišjo prioriteto v korenu kopice (na prvem mestu v tabeli). Element odstranimo in na njegovo mesto postavimo element, ki se nahaja na mestu z največjim indeksom (na zadnjem mestu). Elemente moramo še preurediti tako, da bodo veljale vse lastnosti za kopico. Kazalec zmanjšamo za ena, saj je v tabeli en element manj.

Dane imamo elemente 5,3,2,4,1,8,6,7. Sestavi vrsto s prednostjo s pomočjo kopice. Prioriteta elementa je enaka njegovi vrednosti.

1. korak: Najprej narišemo drevo (kopico) iz podatkov. Narišemo prvo vozlišče.

2. korak:

Narišemo drugo vozlišče, ki je levi sin vozlišča z vrednostjo 5. Vozlišča moramo risati tako, da bo drevo levo zapolnjeno (od leve proti desni).

Ker je vozlišče z vrednostjo 3 manjše od svojega očeta, pustimo drevo tako kot je.

3. korak:

Narišemo naslednje vozlišče.

Ker je tudi vozlišče z vrednostjo 2 manjše od očeta, ne spreminjamo.

4. korak:

Narišemo vozlišče z vrednostjo 4.

Opazimo, da je novo dodano vozlišče večje od svojega očeta z vrednostjo 3. Zamenjamo njuni mesti.

Če pogledamo sedaj drevo, vidimo, da je vsak oče v poddrevesu večji ali enak od svojega sina.

5. korak:

Narišemo naslednje vozlišče iz seznama.

Vozlišče z vrednostjo 1 je manjše od svojega očeta, zato drevesa ne spreminjamo.

Novo dodano vozlišče ima vrednost 8 in je večje od od očeta, zato ju zamenjamo.

Iz drevesa vidimo, da je vozlišče z vrednostjo 8 sin vozlišču z vrednostjo 5, kar pa ni smisleno. Zato ga zamenjamo z njegovim očetom.

Drevo, ki smo ga dobili ustreza lastnostim kopice.

6. korak:

Dodamo naslednje vozlišče.

Ker je novo vozlišče večje od svojega očeta, ju zamenjamo.

7. korak:

Dodamo še zadnje vozlišče iz seznama.

Zadnje vozlišče je večje od svojega očeta in ju zamenjamo.

Ker je vozlišče z vrednostjo 7 spet večje od svojega očeta, zamenjamo njuni mesti.

Drevo, ki smo ga dobili ustreza lastnostim kopice. Torej je vsak sin manjši ali enak svojemu očetu. Dobili smo vrsto s prednostjo.

8. korak:

Iz dobljene vrste s prednostjo ustvarimo tabelo tako, da elemente po vrsti vpišemo od leve proti desni od zgoraj navzdol. Pri ustvarjanju tabele iz kopice moramo paziti,da mesto z indeksom 0 pustimo prazno. Saj bo koren kopice zasedal mesto z indeksom 1.

Ker imamo kopico, je element na mestu z indekosm 1 največji.

Ker pa želimo vrsto s prednostjo predstaviti s pomočjo urejene tabele, ustvarimo novo tabelo (kopico). Element odstranimo iz stare vrste s prednostjo in ga vstavimo v novo. Na njegovo mesto pa postavimo element, ki je v kopici na zadnjem mestu.

Nova kopica je kopica v katero vstavljamo elemente po velikosti (od največjega do najmanjšega). Za sedaj nova vrsta s prenostjovsebuje samo en element z vrednostjo 8.

Nova tabela, ki pripada novi vrsti s prednostjo:

Sedaj pa moramo urediti še prejšnje drevo, ki pa zaenkrat ni več kopica.

Kot že vemo da, če element leži na mestu z indeksom i, potem njegova dva sinova ležita na mestih 2*i in 2*i+1. Gledamo prvi element v tabeli (element v vrednostjo 3 na mestu z indeksom 1). Njegova sinova ležita torej na mestu 2 in 3. Vzamemo prvi element iz tabele in ga zamenjamo z večjim od obeh sinov. Torej zamenjamo elementa z vrednostjo 3 in 7.

Stara tabela, ki pripada stari VSP, ki jo urejamo.

Še vedno opazujemo element z vrednostjo 3. Ker se nahaja na mestu z indeksom 2, se njegova dva sinova nahajata na mestih 4 in 5. Zamenjamo ga z večjim izmed njiju. Torej ga zamenjamo z elementom 4.

Sedaj ima ta element indeks 4, njegova sinova pa 8 in 9. Ker pa je elementov v tabeli samo 7, ta element nima nobenega sina in je zato list.

9. korak:

Dobili smo novo kopico. Izpišemo prvi element iz te kopice (element 7), ga vstavimo v novo VSP in na njegovo mesto postavimo element z vrednostjo 5.

Nova kopica:

Staro drevo uredimo tako, da bo spet postalo kopica.

Kot vidimo imamo v tabeli samo še šest elementov, saj smo dva največja že odstranili in vstavili v novo vrsto s prednostjo.

Sedaj opazujemo element z vrednostjo 5. Ker je manjši od svojega sina, ki se nahaja na mestu z indeksom 3, ju zamenjamo.

Element v korenu primerjamo z njegovima sinovoma in ga zamenjamo z večjim od njiju.

Element je sedaj dobil indeks mesta 3 in njegova sinova sta zdaj na šestem in sedemem mestu. Ker pa je v tabeli samo 6 elementov ima torej element 5 samo enega sina. Ker pa ta ni večji od njega, elementa ne prestavljamo.

10. korak:

Dobili smo novo kopico z največjim elementom v korenu. Ta koren izpišemo v novo tabelo in zadnjega v kopici postavimo na njegovo mesto.

V novo VSP vpišemo največji element iz stare:

Tabela, ki pripada novi VSP:

Dobili smo novo drevo, ki pa ni več kopica. Preuredimo.

Sedaj gledamo element z vrednostjo 2, ki je na mestu z indeksom 1. Ker je manjši od obeh sinov, ga zamenjamo z večjim od njiju.

Element se je prestavil na mesto z indeksom 3. Ker bi njegova sinova morala nastopati na šestem in sedmem mestu, elementov v kopici pa je samo 5, je list. Dobili smo kopico.

11. korak:

Nova VSP, kjer so elementi urejeni po velikosti:

Staro drevo preuredimo v kopico.

Ostali so nam samo še štirje elementi v kopici. Element na mestu z indeksom 1 ima vrednost 1 zato ga zamenjamo z elementom na indeksu 2.

Element je dobil enega sina, ki pa je večji od njega. Zamenjamo njuni mesti.

Ker se je element postavil na zadnje mesto je postal list. Dobimo kopico.

12. korak:

Izpišemo največjega iz tabele in ga vstavim v novo.

Nova vrsta s prednostjo in njej pripradajoča tabela:

Dobimo novo drevo, ki ga preuredimo v kopico.

Na prvo mesto je prišel element z vrednostjo 1. Zamenjamo ga z večjim od sinov. Element postane list in dobimo kopico.

Največjega vstavimo v novo VSP.

Spet dobimo novo drevo, ki ga preuredimo v kopico.

13. korak:

Element na mestu 1 je večji od svojega sina. Zato ga iz te tabele prestavimo v novo VSP.

Stara tabela:

Nova vrsta s prednostjo:

14. korak:

Stara VSP:

V stari tabeli nam ostane samo še en element, ki pa nima sinov. Zato ga prestavimo v vrsto s prednostjo in izbrišemo iz kopice. Dobimo tabelo, kjer so elementi urejeni od največja do najmanjšega.

Dobili smo kopico(tabelo), ki nam predstavlja vrsto s prednostjo. Elementi so urejeni od tistega z najvišjo prioriteto do tistega z najmanjšo.

Sestavi vrsto s prednostjo s pomočjo tabele z naslednjimi podatki: (A,88), (B,100), (C,3), (Č,22), (D,1000), (E,77), (F,82), (G,200), (H,16), (I,333), (J,8000), (K,555), (L,999), (M,55), (N,700), (O,45), (P,5000), (R,10), (S, 150), (Š,650), (T,10000), (U,111), (V,56), (Z,1), (Ž,444).

Vstavljamo elemente po vrsti v tabelo. Na začetku je tabela prazna.

Kazalec=0 (ker ima prvo prosto mesto v tabeli indeks 0)

1. korak:

Najprej vstavimo element (A,88). Ta element ima trenutno največjo prioriteto v tabeli.

Kazalec povečamo za ena

Kazalec=1

2. korak:

Vstavimo element (B,100)

Kazalec=2

Primerjamo prioriteto trenutno vstavljenega elementa z elementom, ki je imel največjo prioriteto. Ker ima novo vstavljeni element večjo prioriteto tabele ne spreminjamo.

3. korak:

Vstavimo element (C,3)

Kazalec=3

Ker je prioriteta vstavljenega elementa manjša od prejšnjega, zamenjamo njuni mesti.

Ker je prioriteta elementa C še vedno od njegovega predhodnika (elementa A), zamenjamo tudi njuni mesti.

Kot vidimo si elementi sledijo od najmanjše prioritete do največje.

4. korak:

Vstavimo naslednji element (Č,22)

Kazalec=4

Ker je prioriteta vstavljenega elementa Č manjša od elementa, ki stoji pred njim v tabeli, zamenjamo njuni mesti.

Še vedno je prioriteta elementa Č manjša od elementa pred njim, zato ju zamenjamo.

Ker je prioriteta elementa Č večja od njegovega levega soseda ne spreminjamo več mest elementov. Vstavim naslednji element iz podatkov.

Postopek nadaljujemo.

10. korak:

Ko vstavimo element (I,333) dobimo naslednjo tabelo.

Kazalec=10

...Nadaljujemo postopek...

19. korak:

Ko vstavimo element (S,150) dobimo naslednjo tabelo.

Kazalec=19

...Nadaljujemo postopek...

24. korak:

Vstavili smo vse elemente v tabelo.

Kazalec=24

Dobili smo vrsto s prednostjo, kjer so elementi razporejeni po prioriteti (od najmanjše do največje).

Sedaj želimo izpisati še element z največjo priotireto.To je element, ki stoji zadnji v tabeli. Njegov indeks je kazalec-1 --> torej stoji na mestu z indeksom 23. Ta element je element J, ki ima prioriteto 1000.

Naloga pa od nas zahteva, da izpišemo še 13 element v vrsti. Ta element stoji na 13-1=12-mestu v tabeli. To je element U s prioriteto 111.

Primer je predstavljen s pomočjo filma.

Preveri

• Jernej Kozak: Podatkovne strukture in algoritmi, DMFA, Ljubljana 1986
• Igor Kononenko, Marko Robnik Šikonja: Algoritmi in podatkovne strukture I, založba FE in FRI, Ljubljana 2003

• http://en.wikipedia.org/wiki/Priority_queue

• http://wiki.fmf.uni-lj.si/wiki/Vrsta_s_prednostjo
• http://penelope.fmf.uni-lj.si/psawiki/index.php/Naloge_iz_seminarskih_nalog/Vrsta_s_prednostjo