N13

13.

Egyesítheto˝ prioritási sor megvalósítása Fibonacci-kupaccal

Értékhalmaz: EPriSor = { S : S ⊆ E}, E -n értelmezett a ≤ lineáris rendezési reláció. Muveletek: ˝

S, S1 , S2 : EPriSor, x : E

{Igaz}

Letesit(S, ≤)

{S = S}

Megszuntet(S)

{S = S}

Uresit(S)

/ {S = 0} {} / {S = 0}

{S = S}

SorBa(S, x)

{S = Pre(S) ∪ {x}}

/ {S 6= 0}

SorBol(S, x)

{x = min(Pre(S)) ∧ Pre(S) = S ∪ {x}}

{S = {a1 , . . . , an }}

Elemszam(S)

{Elemszam = n}

/ {S 6= 0}

Elso(S, x)

{x = min(Pre(S)) ∧ Pre(S) = S}

/ {S 6= 0}

Torol(S)

{S = Pre(S) − {min(Pre(S))}}

/ {S1 = S1 , S2 = S2 } Egyesit(S1 , S2 , S) {S = Pre(S1 ) ∪ Pre(S2 ) ∧ S1 = 0/ ∧ S2 = 0}} public interface EPriSor<E extends Comparable<E>> extends PriSor<E>{ public void Egyesit(EPriSor<E> S2); } Követelmény: (|S| = n, |S1 | = n1 |S2 | = n2 ) S OR B A: Tlr (n) = O(lg n) S OR B OL: Tlr (n) = O(lg n) E GYESIT: Tlr (n1 , n2 ) = O(lg n1 + lg n2 )

13.1.

Az EPrisor megvalósítása balos kupaccal

13.1. definíció. Egy F bináris fa (minimumos) kupac, ha (∀p ∈ F) (Adat(p) ≤ Adat(Bal(p)) ∧ (Adat(p) ≤ Adat(Jobb(p))

13.2. definíció. Az F bináris fa p pontjának rangja; rang(p) = rang(⊥) = 0 rang(p) = 1 + min{rang(Bal(p)), rang(Jobb(p)} ˝ levélig vezeto˝ út hossza. Tehát rang(p) = a legrövidebb, p-bol 13.3. definíció. Az F bináris fa balos-fa, ha (∀p ∈ F)(rang(p) = rang(Jobb(p)) + 1) 13.4. következmény. Ha F balos-fa, akkor a jobb-sarkába vezeto˝ út a legrövidebb, levélhez vezeto˝ út. 13.5. lemma. Bármely F bináris fára |F| ≥ 2rang(F) − 1 Bizonyítás. Bizonyítás rang-szerinti indukcióvak:

rang(F) = 0 akkor F = ⊥, tehát |F| = 0 = 20 − 1 |F| = 1 + |Bal(F)| + |Jobb(F)| ≥ 1 + 2rang(Bal(F)) − 1 + 2rang(Jobb(F)) − 1 ≥ 2 · 2min{rang(Bal(F)),rang(Jobb(F))} − 1 = 2min{rang(Bal(F)),rang(Jobb(F))}+1 − 1 = 2rang(F) − 1

 1

13.6. következmény. Ha F balos-fa, akkor rang(F) ≤ lg(|F| + 1) E GYESÍT rekurzív megvalósítása

1. ábra. Két balos kupac egyesítése.

public class EPriSorBalos<E extends Comparable<E>> implements EPriSor<E>{ private BalosFaPont<E> gyoker; int eszam; private class BalosFaPont<E>{ E elem; BalosFaPont<E> bal, jobb; int rang; BalosFaPont(E x, int rg){ elem=x; rang=rg; } BalosFaPont(){ } } public BalosFaPont<E> FaEgyesit(BalosFaPont<E> p1, BalosFaPont<E> p2){ BalosFaPont<E> p, balfa, jobbfa; int rangb, rangj; if (p1==null) return p2; else if (p2==null) return p1; else{ if (p1.elem.compareTo(p2.elem)<0){ p=p1; balfa=p1.bal; jobbfa=FaEgyesit(p1.jobb, p2); }else{ p=p2; balfa=p2.bal; jobbfa=FaEgyesit(p2.jobb, p1); } rangb = (balfa==null) ? 0 : balfa.rang; rangj = (jobbfa==null) ? 0 :jobbfa.rang; if (rangb
F1

F2

x

y F

α1

β1

α2

JS

β2

x
β1

F2

F

x JS

α1

x≥y

β2

F1

F

y JS

α2

2. ábra. Transzformációs szabályok két balos kupac egyesítéséhez.

3

2. Adat(JobbSarok(F)) ≤ Adat(F1 ), Adat(F2 ) 3. F jobboldali pontjainak kivételével balos-fa

public BalosFaPont<E> NRFaEgyesit(BalosFaPont<E> p1, BalosFaPont<E> p2){ //Két balos-kupac egyesítésének nemrekurzív megvalósítása BalosFaPont<E> JS, OS, p, balfa, jobbfa; int rangb, rangj; if (p1==null) return p2; else if (p2==null) return p1; else{ JS=null; while (p1!=null && p2!=null){ if (p1.elem.compareTo(p2.elem)<0){ jobbfa=p1.jobb; p1.jobb=JS; JS=p1; p1=jobbfa; }else{ jobbfa=p2.jobb; p2.jobb=JS; JS=p2; p2=jobbfa; } }//while jobbfa = (p1==null) ? p2 : p1; rangj = (jobbfa==null) ? 0 : jobbfa.rang; while (JS!=null){ balfa=JS.bal; rangb= (balfa==null) ? 0 : balfa.rang; if (rangbjobb csere JS.bal=jobbfa; jobbfa=balfa; rangb=rangj; } OS=JS.jobb; JS.jobb=jobbfa; jobbfa=JS; JS.rang=rangj+1; JS=OS; }//while return jobbfa; } } public void Egyesit(EPriSor<E> S2){ if (S2 instanceof EPriSorBalos){ BalosFaPont<E> p2=((EPriSorBalos<E>)S2).gyoker; gyoker=NRFaEgyesit(gyoker,p2); eszam+=S2.Elemszam(); }else{ throw new RuntimeException("A két EPrisor nem azonos ábrázolású"); } public void SorBa(E x){

4

BalosFaPont<E> p=new BalosFaPont<E>(x,0); eszam++; gyoker=NRFaEgyesit(gyoker, p); } public E SorBol(){ if (gyoker==null) return null; E x=gyoker.elem; eszam--; gyoker=NRFaEgyesit(gyoker.bal, gyoker.jobb); return x; } public E Elso(){ return (gyoker==null) ? null : gyoker.elem; } public void Torol(){ if (gyoker==null) return; eszam--; gyoker=NRFaEgyesit(gyoker.bal, gyoker.jobb); } }

13.2.

Binomiális kupac

B0

Bk

Bk−1 Bk−1 Bk

B0

...

Bk−1

Bk −2

B1

3. ábra. Binomiális fa definíciója.

Definíció: Binomiális kupac binomiális fák olyan hF1 , . . . , Fk i sorozata, amelyre teljesül: 1. Minden Fi binomiális fa. 2. Minden Fi fa kupac. 3. Nincs két azonos fokszámú fa a sorozatban. ˝ a sorozatban. 4. A fák fokszám szerint növekvoek Lemma. Ha F i-ed fokú binomiális fa, akkor 1. 2i pontja van 2. magassága i
3. az j-edik szinten ij pont van 5

4. jobbról-balra az j-edik fia B j , i = 0, · · · , i − 1 Következmény. Minden n pontú hF1 , . . . , Fk i binomiális kupac esetén k ≤ lg n.

13.3.

Fibonacci-kupac

Definíció:A Fibonacci-kupac H = hF1 , . . . , Fk i 1. Minden Fi fa kupac.

Apa Jobb

Bal EFiu

4. ábra. Fibonacci-kupac fáinak ábrázolása.

private class FibFaPont<E>{ E elem; FibFaPont<E> bal, jobb, apa, efiu; byte fokszam; boolean megjelol=false; FibFaPont(){ } FibFaPont(E x){ elem=x; this.bal=this; this.jobb=this; } } Az adatszerkezetben minden pont fiainak sorozata a bal és jobb pointerekkel kétirányú körláncot képez. Fibonacci-kupaccal ábrázolt egyesítheto˝ prioritási sor a legkisebb kulcsot tartalmazó fa gyökerére mutató pointerrel adott. Jelölje t(H) a H sorozatbeli fák számát, m(H) pedig a megjelölt pontok számát. Definiáljuk a potenciálfüggvényt:

Φ(H) = t(H) + 2 m(H) .

(1)

A muveletek ˝ megvalósítása. E GYESIT(S1,S2, S) A muvelet ˝ egyszeruen ˝ megvalósítható két körlánc közönséges egyesítésével. Egyesítsük a H1 és H2 körláncot, majd H1 .min és H2 .min közül a kisebb kulcsot tartalmazó legyen az egyesített sorozat kijelölt minimum pontja. A muvelet ˝ költsége. A potenciál változása:

6

min[H] (a)

23

7

3 18

52

39

17 38

30

41

24 26

46

35

min[H]

(b)

23

7

3

18

39

52

17

38

41

30

24

26

46

35

5. ábra. Példa fibonacci-kupacra.

7

Φ(H) − (Φ(H1 ) + Φ(H2 )) = (t(H) + 2 m(H)) − ((t(H1 ) + 2 m(H1 )) + (t(H2 ) + 2 m(H2 ))) = 0, ˝ Mivel t(H) = t(H1 ) + t(H2 ) and m(H) = m(H1 ) + m(H2 ). Ezért az amortizált költség a O(1) tényleges költséggel egyenlo. S OR B A(S,x) ˝ egypontú fát, majd egyesítsük az S-t ábrázoló kupaccal. Képezzünk a beszúrandó x elembol A muvelet ˝ költsége. A potenciál növekedése:

((t(H) + 1) + 2 m(H)) − (t(H) + 2 m(H)) = 1 . Mivel a tényleges költség O(1), az amortizált költség O(1) + 1 = O(1). Tegyük fel, hogy a fokszámokra ismert egy D(H.n) felso˝ korlát. (Megmutatjuk majd, hogy ez O(lg n).) S OR B OL(S,x) begin z:=H.min; if z=Nil then return z; for z minden x fiára do begin x-et tegyük H gyökérlistájába; x.apa:=Nil end vegyük ki z-t H gyökérlistájából; if z=z.jobb then H.min:=Nil else begin H.min:=z.jobb; Kiegyenlit(H); end; H.n:=H.n-1; end;

K IEGYENLIT(H) begin for i:=1 to D(H.n) do A[i]:=Nil; for H minden w fájára do begin x:=w; d:=x.fokszam; while A[d]<>Nil do begin y:=A[d]; if x.kulcs > y.kulcs then Csere(x,y); KupacotSzerkeszt(H,y,x); A[d]:=Nil; d:=d+1; end; A[d]:=x; end; H.min:=Nil; for i:=1 to D(H.n) do if A[i]<>Nil then begin Tegyük A[i]-t H-ba; if (H.min=Nil) Or (A[i].kulcs < H.min.kulcs) then H.min:=A[i] ; end; end 8

K UPACOT S ZERKESZT(H,y,x) begin vegyük ki y-t H-ból; tegyük y-t x egy fiává és növeljük x fokszámát; x.megjelöl:=Hamis; end;

Állítás. SorBol muvelet ˝ amortizált költsége O(D(H.n)). A gyökérlista mérete legfeljebb D(n) + t(H) − 1, így az aktuális költség O(D(n) + t(H)). ˝ t(H) + 2m(H), a kivágás után D(n) + 1 + 2m(H). A potenciál a min. pont kivágása elott

O(D(n) + t(H)) + ((D(n) + 1) + 2 m(H)) − (t(H) + 2 m(H)) = O(D(n)) + O(t(H)) − t(H) = O(D(n)) M ODOSIT(H,x,k) begin if k > x.kulcs then begin hiba "az új kulcs nagyobb, mint az aktuális"; exit end; x.kulcs:=k; y:=x.apa; if (y<>Nil) and (x.kulcs < y.kulcs) then begin K IVAG (H, X , Y ); K ASZKADVAGAS (H, Y ); end; if x.kulcs < H.min.kulcs) then H.min:=x; end; end; K IVAG(H,x,y) begin vegyük ki x-et y fiainak láncából; y.fokszam:=y.fokszam-1; tegyük x-et H gyökérlistájába; x.apa:=Nil; x.megjelöl:=Hamis; end;

K ASZKADVAGAS(H,y) begin z:=y.apa; if z<>Nil then begin if y.megjelöl=Hamis then y.megjelöl=Igaz else begin K IVAG(H,y,z); K ASZKADVAGAS(H,z) end; end; end;

9

A M ODOSIT algoritmus futási idejének elemzése. A tényleges költség kiszámítása. Tegyük fel, hogy M ODOSIT adott hívására c számú K ASZKADVAGAS hajtódik végre. Ekkor M ODOSIT tényleges futási ideje O(c). A potenciál változás: A K ASZKADVAGAS minden hívása, az utolsó kivételével, kivesz egy fapontot a fából és beteszi azt H gyökérlistájába. Így a K ASZ KADVAGAS -ok végrehajtása után t(H) + c fa lesz a gyökérlistában (t(H) volt eredetileg, az x pont, és c − 1 pont került be a vágások eredményeként). Legfeljebb m(H) − c + 2 pont lesz megjelölve, mert c − 1 pont jelöletlenné vált a K ASZKADVAGAS-ok miatt, és esetleg egyet még jelöletlenné tesz. A potenciál változása

((t(H) + c) + 2(m(H) − c + 2)) − (t(H) + 2 m(H)) = 4 − c . Tehát a M ODOSIT eljárás amortizált futási ideje legfeljebb

O(c) + 4 − c = O(1) 13.3.1.

A maximális fokszám felso˝ korlátja

˝ 13.7. lemma. Legyen x a H Fibonacci-kupac tetszoleges pontja, amelynek fokszáma k (x. f okszam = k). Jelölje az y1 , y2 , . . . , yk ˝ sorozat x fiait abban az idorendi sorrendben, ahogyan x fiai lettek. Ekkor y1 . f okszam ≥ 0 és yi . f okszam ≥ i − 2 i = 2, . . . , k-ra. Bizonyítás. A y1 . f okszam ≥ 0 állítás nyilvánvaló. i ≥ 2 esetén vegyük észre, hogy amikor yi -t x-hez kapcsoltuk annak fiaként, akkor már az y1 , . . . , yi−1 pontok x fiai voltak, így az x. f okszam = i − 1 fennállt. Az yi pontot csak akkor kapcsoltuk x-hez, ha ˝ yi . f okszam = x. f okszam, tehát yi . f okszam = i − 1 is teljesült. Azóta yi legfeljebb egy fiát veszthette el, mert egyébként x-bol kivágták volna. Tehát yi . f okszam ≥ i − 2. Tekintsük a következo˝ Fibonacci számsorozatot.   0 ha k = 0 ,  Fk = 1 ha k = 1 ,  Fk−1 + Fk−2 ha k ≥ 2 . 13.8. lemma. Minden k ≥ 0 egész számra k

Fk+2 = 1 + ∑ Fi . i=0

Bizonyítás. k-szerinti indukcióval bizonyítunk. k = 0-ra 0

1 + ∑ Fi

= 1 + F0

i=0

= 1+0 = 1 = F2 . Az indukciós feltétel szerint Fk+1 = 1 + ∑k−1 i=0 Fi , tehát

Fk+2

= Fk + Fk+1 k−1

= Fk + 1 + ∑ Fi

!

i=0

k

= 1 + ∑ Fi i=0

 13.9. lemma. Minden k ≥ 0 egész számra Fk+2 ≥ Φk . Bizonyítás. Bizonyítás k-szerinti √ indukcióval. F2 = 1 = Φ0 , F3 = 2 ≥ (1 + 5)/2 = Φ1 . Ha 2, · · · , k − 2-ig áll az ≤ Fk+2 = Fk + Fk+1 ≥ Φk−2 + Φk−1 = Φk−2 (1 + Φ). Mivel a Φ2 = (1 + Φ) azaz (Φ2 − Φ − 1 = 0) egyenlet megoldása Φ = Fk+2 ≥ Φk−2 Φ2 = Φk .

10

√ 1+ 5 2

t 1.618, így



˝ 13.10. lemma. Legyen x a H Fibonacci-kupac tetszoleges pontja, amelynek √ fokszáma k (x. f okszam = k). Jelölje méret(x) az x-gyökeru˝ részfa pontjainak számát. Ekkor méret(x) ≥ Φk , ahol Φ = (1 + 5)/2. Bizonyítás. Jelölje sk a legkevesebb pontot tartalmazó Fibonacci-kupac olyan fáját, amelynek fokszáma k, tehát a minimumát a méret(z) értékeknek, ahol z. f okszam = k. Nyilvánvaló, hogy s0 = 1, s1 = 2, s2 = 3. sk értéke legfeljebb méret(x) lehet, és értéke ˝ Jelölje most is az y1 , y2 , . . . , yk sorozat x fiait abban az idorendi ˝ k-szerint monoton no. sorrendben, ahogyan x fiai lettek. Alsó korlátot adunk méret(x)-re, úgy, hogy összeszámláljuk pontjait: méret(x)

≥ sk k

= 2 + ∑ syi . f okszam i=2 k

≥ 2 + ∑ si−2 i=2

k-szerinti indukcióval megmutatjuk, hogy sk ≥ Fk+2 minden k nemnegatív egész számra. A k = 0 és k = 1 eset nyilvánvaló. Feltéve, hogy k ≥ 0 esetén i = 0, 1, . . . , k − 1-re si ≥ Fi+2 igaz, kapjuk, hogy k

sk

≥ 2 + ∑ si−2 i=2 k

≥ 2 + ∑ Fi i=2 k

= 1 + ∑ Fi i=0

= Fk+2 .



Tehát méret(x) ≥ sk ≥ Fk+2 ≥ Φk . ˝ 13.11. következmény. Egy n pontot tartalmazó Fibonacci-kupac tetszoleges pontjának D(n) maximális fokszáma O(lg n).

˝ Bizonyítás. Legyen x egy n pontot tartalmazó Fibonacci-kupac tetszoleges pontja, és legyen x. f okszam = k. A (7.9) lemma k . Φ alapú logaritmusát véve kapjuk, hogy k ≤ log n. (Pontosabban, mivel k egész szám, állítása szerint n ≥ méret (x) ≥ Φ Φ j k

k ≤ logφ n .) Így bármely pont D(n) maximális fokszáma O(lg n). Megvalósítás

public class EPriSorFib<E extends Comparable<E>> implements EPriSor<E>{ protected FibFaPont<E> minPont; private int eszam; private static final byte MaxFok=64; private FibFaPont<E>[] A= new FibFaPont[MaxFok]; private class FibFaPont<E>{ E elem; FibFaPont<E> bal, jobb, apa, efiu; byte fokszam; boolean megjelol=false; FibFaPont(){ } FibFaPont(E x){ elem=x; this.bal=this; this.jobb=this; } }

11



public void Uresit(){ minPont=null; eszam=0; } public int Elemszam(){ return eszam; } public void SorBa(E x){ FibFaPont<E> p=new FibFaPont<E>(x); eszam++; LancBa(minPont, p); if (p.elem.compareTo(minPont.elem)<0) minPont=p; } public E SorBol(){ if (eszam==0) return null; FibFaPont<E> z=minPont; E e=z.elem; eszam--; if (eszam==0){ minPont=null; return e; } if (z.jobb==z){ minPont=null; }else{ minPont=minPont.jobb; LancBol(z); } z=z.efiu; FibFaPont<E> x; if (z!=null){ do{ x=z.bal; LancBol(x); x.apa=null; LancBa(minPont, x); }while(x!=z); } Kiegyenlit(); return e; } public void Egyesit(EPriSor<E> S2){ if (S2 instanceof EPriSorFib){ FibFaPont<E> p2=((EPriSorFib<E>)S2).minPont; if (minPont==null){ minPont=p2; eszam=S2.Elemszam(); }else if (p2!=null){ FibFaPont<E> p1kovet=minPont.bal; FibFaPont<E> p2kovet=p2.bal; minPont.bal=p2kovet; p2.bal=p1kovet; p2kovet.jobb=minPont; p1kovet.jobb=p2; eszam+=S2.Elemszam(); if (minPont.elem.compareTo(p2.elem)>0 ) minPont=p2; } 12

}else throw new RuntimeException("A két EPriSor nem azonos ábrázolású"); } private void LancBa(FibFaPont<E> p, FibFaPont<E> q){ if (p==null){ q.bal=q; q.jobb=q; minPont=q; return; } FibFaPont<E> pbal=p.bal; q.bal=pbal; q.jobb=p; p.bal=q; pbal.jobb=q; } private void LancBol(FibFaPont<E> p){ if (p.bal==p) return; FibFaPont<E> pbal=p.bal; FibFaPont<E> pjobb=p.jobb; pjobb.bal=pbal; pbal.jobb=pjobb; p.bal=p; p.jobb=p; if (p.apa!=null && p.apa.efiu==p) p.apa.efiu=pbal; } private void Fiava(FibFaPont<E> p, FibFaPont<E> q){ if (p.fokszam==0){ q.bal=q; q.jobb=q; p.efiu=q; }else LancBa(p.efiu, q); q.apa=p; p.fokszam++; } private int log (int n) { int i = 1; int logn = 0; while (i < n) { i = i<<1; logn++; } return logn; } private void Kiegyenlit(){ int maxfok = 2*log(eszam); for (int i=0; i<=maxfok; i++) A[i]=null; FibFaPont<E> w=minPont; FibFaPont<E> x, y, z; int d; do{ w=minPont.bal; LancBol(w); x=w; d=x.fokszam; while (A[d]!=null){ 13

y=A[d]; if (y.elem.compareTo(x.elem)<0 ){ z=x; x=y; y=z; } Fiava(x, y); x.megjelol=false; A[d]=null; d++; } A[d]=x; }while(minPont!=w); minPont=null; for (int i=0; i<=maxfok; i++){ if (A[i]!=null){ A[i].apa=null; LancBa(minPont, A[i]); if (A[i].elem.compareTo(minPont.elem)<0) minPont=A[i]; } } } } A Módosítható prioritási sor megvalósítása Fibonacci-kupaccal.

public class ModPriSorFib<S extends Comparable<S>> implements ModPriSor<S> { private FibFaPont<S> minPont; private int eszam; private int holm=100; private static byte MaxFok=64; private FibFaPont<S>[] A=new FibFaPont[MaxFok]; private FibFaPont<S>[] hol=new FibFaPont[holm]; private class FibFaPont<S extends Comparable<S>>{ KulcsPar elem; FibFaPont<S> bal, jobb, apa, efiu; byte fokszam; boolean megjelol=false; FibFaPont(){ } FibFaPont(KulcsPar x){ elem=x; this.bal=this; this.jobb=this; } } public void Modosit(KulcsPar x){ if (x.kulcs<0 || x.kulcs>=holm || hol[x.kulcs]==null) throw new RuntimeException("Nincs ilyen elem"); FibFaPont<S> px=hol[x.kulcs]; if (px.elem.adat.compareTo(x.adat)<0){ throw new RuntimeException("Csak csökkenteni lehet"); } 14

px.elem=x; FibFaPont<S> y=px.apa; if (y!=null && x.adat.compareTo(y.elem.adat)<0){ Kivag(px,y); KaszkadVagas(y); } if (x.adat.compareTo(minPont.elem.adat) <0) minPont=px; } private void Kivag(FibFaPont<S> x, FibFaPont<S> y){ //x.apa==y LancBol(x); y.fokszam--; x.apa=null; x.megjelol=false; LancBa(minPont, x); } private void KaszkadVagas(FibFaPont<S> y){ FibFaPont<S> z=y.apa; if (z==null) return; if (!y.megjelol){ y.megjelol=true; }else{ Kivag(y, z); KaszkadVagas(z); } } public void Eltavolit(KulcsPar x){ if (x.kulcs<0 || x.kulcs>=holm || hol[x.kulcs]==null) throw new RuntimeException("Nincs ilyen elem"); FibFaPont<S> px=hol[x.kulcs]; if (px==minPont){ SorBol(); return; } FibFaPont<S> y=px.apa; if (y!=null ){ if (px==y.efiu) y.efiu=px.bal; y.fokszam--; LancBol(px); }else LancBol(px); px=px.efiu; FibFaPont<S> z; if (px!=null){ do{z=px.bal; LancBol(z); z.apa=null; LancBa(minPont, z); }while(z!=px); Kiegyenlit(); } eszam--; }

15