7
Prioritetna vrsta je zbirka elementov s temi operacijami:
Ustvari(pvrsta)
: Ustvari prazno prioritetno vrsto.Dodaj(pvrsta, element)
: Doda element v prioritetno vrsto (ni pomembno, na kateri položaj).Odvzemi(pvrsta)
: Odstrani največji element iz vrste in ga vrne kot rezultat. Če je takih elementov več, ni pomembno, katerega od njih odstrani.JePrazna(pvrsta)
: Vrne True
, če je prioritetna vrsta prazna, sicer pa vrne False
.Na primer, če v prazno prioritetno vrsto dodamo elemente 50, 70, 20 in 60 ter potem štirikrat zaporedoma kličemo funkcijo Odvzemi
, bo prvi klic odstranil in vrnil element 70, drugi element 60, tretji element 50, četrti pa element 20. Kljub svojemu imenu prioritetna vrsta ni vrsta. Pravzaprav niti zaporedje ni, saj vrstni red dodajanja elementov ni bistven.
Če prioritetno vrsto implementiramo s pomočjo tabele, imamo dve možnosti: (1) dodajanje v času O(1) in odvzemanje v času O(n); (2) dodajanje v času O(n) in odvzemanje v času O(1). V obeh primerih je n število elementov v prioritetni vrsti. Sprogramiraj in preizkusi obe možni implementaciji!
Opomba: Obstajajo tudi učinkovitejše, a bolj zapletene implementacije prioritetne vrste, v katerih tako dodajanje kot odvzemanje zahtevata čas O(log n).