Vrsta s prednostjo

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?


Vsebina

Definicija

Vrsta s prednostjo je podatkovna struktura, ki jo običajno implementiramo s kopico. V vrsto s prednostjo vstavljamo elemente, ki nosijo ob sebi tudi podatek, ki mu pravimo prednost. Ko elemente jemljemo iz vrste, odstranimo tistega, ki ima največjo prednost.

Predstavitev vrste s prednostjo

Operacije

Osnovne operacije:

  • dodaj(insertItem)
  • najmanjši(minKey)
  • odreži(delMin)

poleg teh imamo običajno še naslednje operacije:

  • tvorjenje
  • uničevanje
  • osnovna poizvedovanja(velikost, ime,...)

Primer uporabe vrste s prednostjo

Primer operacije nad dvojiško kopico:

  • predmet dodamo kot list
  • predmet polzi navzgor proti korenu, dokler je potrebno

  1. public void insert(comparable elt) {
  2. int i;
  3. int iNew;
  4. elts[size] = elt;
  5. i = size; i++;
  6. iNew = i/2;
  7. while (i>0) && (elts[i].compare(elts[iNew]) < 0) {
  8. swap(i, iNew);
  9. i = iNew;
  10. iNew = iNew/2;
  11. }
  12. }//insert


Primer urejanja (sortiranje):

S pomočjo vrste s prednostjo lahko uredimo (sortiramo) polje elementov. To storimo v dveh korakih:

  • vse elemente polja vstavimo v vrsto s prednostjo
  • pobiramo elemente iz vrste s prednostjo, dokler ni prazna

  1. Sort(int polje[])priorityQueue pq = new priorityQueue(polje.length);
  2. for (i= 0; i < polje.length; i++) {
  3. pq.insertItem(polje[i], null);
  4. }
  5. for (i= 0; i < polje.length; i++) {
  6. polje[i]= pq.minKey();
  7. pq.delMin();
  8. }
  9. } // Sort
  10.  



Primer uporabe v Mathematici


Clear[Pripravi, Vstavi, JePrazna, Najvecji, Odstrani, Zlij];
JePrazna[Pripravi[]] := True;
JePrazna[Vstavi[v_, e_]] := False;

Najvecji[Pripravi[]] := Null;
Najvecji[Vstavi[v_, e_]] /; JePrazna[v] := e;
Najvecji[Vstavi[v_, e_]] := Max[Najvecji[v], e];

Odstrani[Pripravi[]] := Pripravi[];
Odstrani[Vstavi[Pripravi[], e_]] := Pripravi[];
Odstrani[Vstavi[v_, e_]] := Odstrani[Vstavi[v, e], Najvecji[v]];
Odstrani[Vstavi[v_, e_], m_] /; e == m := v;
Odstrani[Vstavi[v_, e_], m_] := Vstavi[Odstrani[v, m], e];

Zlij[v_, Pripravi[]] := v
Zlij[Pripravi[], v_] := v
Zlij[Vstavi[v_, e_], v1_] := Zlij[v, Vstavi[v1, e]]


Primer


Clear[v, t]
v = Vstavi[Vstavi[Vstavi[Pripravi[], 3], 1], 2]

Vstavi[Vstavi[Vstavi[Pripravi[], 3], 1], 2]

Izvedba vrste s prednostjo

  • Najpreprostejša izvedba je seznam. Imamo dve možnosti
  1. elemente vedno dodajamo na začetku
  2. elementi v seznamu so urejeni po velikosti

Pri prvi inačici je zelo preprosto dodajati elemente O(1): seznam = (nov element, seznam)pri tem pa je veliko težje najti najmanjši ključ, saj moramo preiskati cel seznam O(n).

Za drugo inačico pa je ravno obratno, saj za vstavljanje porabimo O(n), za iskanje najmanjšega ključa pa le O(1) časa.

  • druga možnost pa je izvedba s kopico.

Zunanji viri

Osebna orodja