Queap

U informatici, "queap" je red sa prioritetom. Ovaj tip podataka dozvoljava ubacivanje i brisanje elemenata, a podržava i vraćanje elementa najvećeg prioriteta. Svako brisanje traje logaritamski u odnosu na broj elemenata koji su duže u strukturi od elementa koji brisemo. Ubacivanje je konstantne vremenske složenosti.

Ova struktura podataka se sastoji od duplo povezane liste i 2-4 stabla, gde su obe strukture modifikovane da prate element minimalnog prioriteta. Osnovne operacije ove strukture održavaju dodate elemente u duplo povezanu listu, dok se ne izvrši brisanje elementa, kada se svi elementi smeste u 2-4 stablo. 2-4 stablo čuva svoje elemente u insertnom poretku umesto u pogodnijem poretku prioriteta.

Ovaj tip podataka su osmislili i imenovali John Iacono i Stefan Langerman.

Opis

Queap je red sa prioritetom u koji se elementi ubacuju u O(1) vremenu, a brišu minimalni elementi u O(log(k+2)) vremenu ako ima k elemenata koji su bili u hipu duže od elementa koji se briše. Queap ima svojstvo koje se zove svojstvo queap-a: vreme koje je potrebno da se nađe neki element x je O(lg(q(x))) gde je q(x) jednako n-1-w(x) a w(x) je broj elemenata kojima je pristupljeno operacijama kao sto su operacija pretrage, brisanja ili ubacivanja. q(x) se definise kao broj elemenata kojima nije pristupano od poslednjeg pristupa elementu x. Vreme za pronalaženje elmenta je O(lg(w(x))).

Qweap se moze predstaviti preko dva tipa podataka: duplo povezane liste i modifikovane verzije 2-4 stabla. Duplo povezana lista se koristi za instrukcije ubacivanja i lociranja minimalnog elementa. Queap čuva pokazivač na minimalni element u listi. Da bi se dodao neki element u listu, taj element se dodaje na kraj liste i bitovska varijabla u tom elementu se postavlja na jedan. Ovo se vrši kako bi se znalo da li je element u listi ili 2-4 stablu.

2-4 stablo služi kada se vrši operacija brisanja. Ako je element već u stablu, element se brise iz 2-4 stabla. Inače, element je u listi(proverava se preko bitovske varijable).Svi elementi sadržani u listi su onda dodaju u 2-4 stablo, usput postavljajući bitovske varijable na nule.Element je tad odstranjen iz stabla.

Queap koristi samo svojstva 2-4 stabla, ne i stablo pretrage. 2-4 stablo se modifikuje na sledeći način. Pretpostavimo da lista ima skup od k elemenata. Kada se operacija brisanja pozove, skup elemenata sačuvan u listi se onda dodaje na listove 2-4 stabla,nastavljajući se listom koji sadrži ključ beskonacnosti. Svaki internodalni čvor stabla ima pokazivac h(v) koji pokazuje na najmanji element podstabla v. Svaki internodalni čvor na putu P od korena ima pokazivac c(v), koji pokazuje na najmanji kljuc u $T-T_{v}-\{r\}$. h(v) pokazivaci na svaki internodalni cvor na putu P se ignorisu. Queap ima pokazivac na c od korena koji pokazuje na najanji element.

Aplikacija queapova ukljucuje jedinstveni skup događaja velikih prioriteta i izdvajanja događaja velikih prioriteta za obradu.

Operacije

Neka MinL bude pokazivač na minimalni element u duplo povezanoj listi L, a c(x0) bude minimalni element čuvan u 2-4 stablu T,k nek bude broj elementa cuvanih u 2-4 stablu T i neka n bude broj svih elemenata u queap-u Q. Operacije su sledece:

New(Q): Stvara novi prazni queap.

Stvara praznu duplo povezanu listu L i 2-4 stablo T. k i n su nula.

Insert(Q,x): Dodaje element x na queap Q.

Dodaje element x u listu L. Postavlja bitovsku varijablu elementa x na jedan da bi se znalo da je element u listi L. Azurira se minL pokazivač ako je x najmanji element u listi. Povećavamo n za jedan.

Minimum(Q): Vraća pokazivač na najmanji element iz Queap-a Q.

Ako ključ(minL) < ključ(c(x0)), vrati minL.Inače vrati c(x0).

Delete(Q,x): Odstranjuje element x iz queap-a Q.

Ako je bit elementa postavljen na jedan, element se nalazi u listi L. Dodaju se svi elementi iz L u T, postavljajući bit svakog elementa na nulu. Svaki element se dodaje roditelju najdesnijeg deteta od T koristeci operaciju dodavanja elemenata u 2-4 stablo. L postaje prazan. Ažurira h(v) pokazivace na sve čvorove čija su deca sad modifikovana, i ponavlja proces sa sledećim roditeljem dokle god roditelj nije koren. Hoda se od korena ka čvoru x0 i ažuriraju se c(v) vrednosti. k je jednako n.

Ako je bit elementa x nula, x je onda list od T. Brise se x koristeći operaciju za brisanje elemenata u 2-4 stablu. Počevši od čvora x, hoda se u T do čvora x0, ažurirajući h(v) i c(v) pokazivače. Smanjuju se k i n za 1.

DeleteMin(Q):Briše se i vraća najmanji element iz queap-a Q.

Poziva se operacija Minimum(Q). Operacija vraća najmanji element min. Poziva se operacija Delete(Q,min).Vraca min.

CleanUp(Q): Briše sve elemente u listi l i stablu T.

Počevsi od prvog elementa u listi L, prelazi se cela lista,brišući se elementi iste.

Počevsi od korena stabla T, prelazi se stablo, brišući se svaki čvor iz stabla.

Analiza

Vreme izvršavanja se analizira korišćenjem amortizovane analize. Potencijalna funkcija za queap Q će biti $\phi (Q)=c|L|$ gde je $Q=(T,L)$. Insert(Q,x): Cena operacije je O(1).Velicina liste raste za jedan, potencijal raste za neku konstantu c. Minimum(Q): Ova operacija ne menja strukturu tako da je amortizovana cena jednaka pravoj ceni, O(1). Delete(Q,x):Postoje dva slučaja.

Prvi slučaj

Ako je element x u stablu T, onda je cena O(1). Čim je element obrisan iz stabla, pokazivači moraju da se ažuriraju. Najviše će biti O(lg q(x)) ažuriranja.

Drugi slučaj

Ako je element u listi, onda se svi elementi iz liste L smeštaju u stablo T. Cena ovoga je $a|L|$ od neke konstante a. Posle ubacivanja i ažuriranja pokazivača, vreme koje je potrošeno je $2a|L|$. Sledi brisanja elementa iz stabla, i šetnja kroz stablo sa usputnim korigovanjem pokazivača. Vreme potrošeno je najviše $2a|L|+O(lgq(x))$. Ako je c>2a onda je cena O(lgq(x)).

Primer koda

Primer implementacije queap-a u javi:

public class Queap
{
        public int n, k;
        public List<Element> l; //Element is a generic data type
        public QueapTree t;    //a 2-4 tree, modified for Queap purpose
        public Element minL;

        private Queap() {
                n = 0;
                k = 0;
                l = new LinkedList<Element>();
                t = new QueapTree();
        }

        public static Queap New() {
                return new Queap();
        }

        public static void Insert(Queap Q, Element x) {
                if (Q.n == 0)
                        Q.minL = x;
                Q.l.add(x);
                x.inList = true;
                if (x.compareTo(Q.minL) < 0)
                        Q.minL = x;
        }

        public static Element Minimum(Queap Q) {
                //t is a 2-4 tree and x0, cv are tree nodes.
                if (Q.minL.compareTo(Q.t.x0.cv.key) < 0)
                        return Q.minL;

                return Q.t.x0.cv.key;
        }

        public static void Delete(Queap Q, QueapNode x) {
                Q.t.deleteLeaf(x);
                --Q.n;
                --Q.k;
        }

        public static void Delete(Queap Q, Element x) {
                QueapNode n;
                if (x.inList) {
                        //set inList of all the elements in the list to false
                        n = Q.t.insertList(Q.l, x);
                        Q.k = Q.n;
                        Delete(Q, n);
                }
                else if ((n = Q.t.x0.cv).key == x)
                        Delete(Q, n);
        }

        public static Element DeleteMin(Queap Q) {
                Element min = Minimum(Q);
                Delete(Q, min);
                return min;
        }
}

Vidi još

• Листа (структура података)
• 2-3-4 стабло