Egyesíthet˝o prioritási sor Értékhalmaz: EPriSor = S ⊆ E, E-n értelmezett a ≤ lineáris rendezési reláció. M˝uveletek: S, S1 , S2 : EPriSor, x:E / • {Igaz} Letesit(S,≤) {S = 0} • {S = S} Megszuntet(S) {} / • {S = S} Uresit(S) {S = 0} • {S = S} SorBa(S,x) {S = Pre(S) ∪ {x}} / SorBol(S,x) {x = min(Pre(S)) ∧ Pre(S) = S ∪ {x}} • {S 6= 0} • {S = {a1 , . . . , an }} Elemszam(S) {Elemszam = n} / Elso(S,x) {x = min(Pre(S)) ∧ Pre(S) = S} • {S 6= 0} / Torol(S) {S = Pre(S) \ {min(Pre(S))}} • {S 6= 0} / • {S1 = S1 , S2 = S2 } Egyesit(S1 , S2 , S) {S = Pre(S1 ) ∪ Pre(S2 ) ∧ S1 = 0/ ∧ S2 = 0}} Módosítható EPriSort vizsgálunk, amelyben használjuk a KulcsotCsokkent(S,x,k) m˝uveletet, ami x kulcsát a k értékre csökkenti, ha k < kulcs(x), és az AltTorol(S,x) m˝uveletet, amely az x elemet törli az egyesíthet˝o prioritási sorból. Mindkét m˝uveletnél feltesszük, hogy x-et egy rá mutató pointer adja meg. Binomiális fák A binomiális fákat a következ˝o rekurzív definícióval adhatjuk meg. A B0 fa egyetlen pontot tartalmaz. A Bk fa (k ≥ 1) pedig két összekapcsolt Bk−1 fából áll, az egyik fa gyökércsúcsa a másik fa gyökércsúcsának a legbaloldalibb gyereke lesz. Lemma Bi -re a következ˝o állítások teljesülnek i ≥ 1 esetén: 1. 2i pontja van 2. magassága i 3. az j-edik szinten
i j
pontja van
4. jobbról-balra a gyökér j-edik fia B j−1 , j = 1, . . . , i Bizonyítás. Teljes indukcióval. Az indukciós lépés a 3. tulajdonság esetén a binomiális együtthatók ismert i−1 i−1 i + = j j−1 j összefüggése alapján adódik, a többi tulajdonság esetén nyilvánvaló. Binomiális kupac Definíció: Egy fát kupacnak nevezünk, ha minden pontra igaz, hogy a kulcsa nem nagyobb a fiai kulcsainak a minimumánál. Definíció: Egy S binomiális kupac binomiális fák olyan {B1 , . . . , Bk } sorozata, amelyre teljesül: 1. Minden Bi binomiális fa. 1
2. Minden Bi fa kupac. 3. Nincs két azonos fokszámú fa a sorozatban. 4. A fák fokszám szerint növekv˝oek a sorozatban. A binomiális fák pontszámára vonatkozó lemma alapján: Következmény: Minden n pontú {F1 , . . . , Fk } binomiális kupac esetén k ≤ log2 n. Az egyes binomiális fákat els˝ofiú testvér ábrázolással tároljuk. A binomiális fák gyökérelemeit egy láncban tároljuk, amelynek kezd˝opontját Fej(S) adja meg, a láncban a rákövetkez˝o elemre a testver mutató mutat. Elso(S,x) A gyökérlista elemein kell végigmenni és kiválasztani a minimálisat. Elso(S,x) x:=Nil y:=Fej(S) min:=Inf while(y!=Nil) if kulcs(y)<min then min:=kulcs(y) x:=y y:=Testver(y) return x A futási id˝o a gyökérlista hosszával arányos, így legrosszabb esetben O(log n). Egyesit(S,Q,R) Az egyesítés során többször használjuk két Bk−1 fa összekapcsolását, az alábbi eljárás az y gyökércsúcsú fát rakja a z gyökércsúcsú fa alá. BinKapcsol(y,z) apa(y):=z testver(y):=Efiu(z) Efiu(z):=y fokszam(z):=fokszam(z)+1 Szintén használjuk a BinKupFesul(S,Q) eljárást, amely S-nek és Q-nak a gyökérlistáját fésüli össze, a fokszám szerint. Az Egyesit algoritmus els˝oként összefésüli a két gyökérlistát, majd végigmegy a közös listán, és a BinKapcsol eljárás segítségével gondoskodik róla, hogy ne legyen olyan fokszám, amely fokszámhoz két binomiális fa is tartozik. Az alapgondolat az, hogy ha az adott fokszámmal kett˝o fa van, akkor összekapcsolja o˝ ket egy nagyobb fokszámúvá, ha pedig három van (ilyen eset két fa összekapcsolása után jöhet létre), akkor a másodikat és harmadikat kapcsolja össze. Az algoritmus futási ideje O(log(n), mivel az összefésülésnél csak egyszer kell végigmenni a két listán, majd az Egyesit eljárásban egyszer az összefésült listán.
2
Egyesit(S,P,Q) Letesit(Q: EPriSor(BinKupac)) fej(Q):=BinKupFesul(S,P) If fej(Q):=Nil then Return Q megeloz(x):=Nil x:=fej(Q) kovet(x):=testver(x) while(kovet(x)!=Nil) if (fokszam(x)!=fokszam(kovet(x))or (tesver(kovet(x)!=Nil) and fokszam(testver(kovet(x)))=fokszam(x)) then megeloz(x):=x x:=kovet(x) else if kulcs(x)
Az algoritmus a kupac MaxKupacol eljárásához hasonló ötlet alapján cserékkel felfele mozgatja az elemet addig, amíg a kupac tulajdonság helyre nem áll. KulcsotCsokkent(S,x,k) if k>kulcs(x) Then write "hibas adat" return kulcs(x):=k y:=x z:=apa(x) while(z!=Nil and kulcs(y)
Az amortizált elemzés során feltételezzük, hogy adott egy D(n) fels˝o korlát az n pontot tartalmazó Fibonacci kupacban szerepl˝o csúcsok maximális fokszámára. Igazolni fogjuk, hogy D(n) = O(log(n)). Egyesít(S,Q,R) Az Egyesít m˝uvelet során a gyökérlistákat tartalmazó két körláncot kell egyesíteni, majd a min(S) és min(Q) pontok közül a kisebb kulcsot tartalmazó pontot választjuk az egyesített gyökérlista kijelölt minimum pontjának. A muvelet ˝ költsége. A potenciál változása: Φ(R) − (Φ(S) + Φ(Q)) = (t(R) + 2m(R)) − ((t(S) + 2m(S)) + (t(R) + 2m(R))) = 0, hiszen t(R) = t(S) + t(Q) és m(R) = m(S) + m(Q). Ezért az amortizált költség a tényleges költséggel egyenl˝o, azaz O(1). SORBA(S,x) Képezzünk a beszúrandó x elemb˝ol egy egypontú fát, majd az ebb˝ol a fából álló Fibonacci kupacot egyesítsük S-el. A muvelet ˝ költsége. A potenciál változása: ((t(S) + 1) + 2m(S)) − (t(S) + 2m(S)) = 1. A tényleges költség O(1), így az amortizált költség O(1) + 1 = O(1). Sorbol(S,x) Az algoritmus a minimum elem fiait átrakja a gyökérlistába, majd végrehajtja a KIEGYENLIT eljárást. Sorbol(S,x) z:=min(S) if z=Nil then return z for z minden x fiára x-et tegyük S gyökérlistájába apa(x):=Nil vegyük ki z-t S gyökérlistájából if z=jobb(z) /egy pont volt a fában then min(S):=Nil else min(S):=jobb(z) Kiegyenlit(S) n(S):=n(S)-1; A Kiegyenlit használja a FibKupSzerk(S,y,x) eljárást, ami az y gyöker˝u fát berakja az x gyöker˝u fa alá. Továbbá felhasznál egy A tömböt, amelynek a mérete D(n) és amelyre A[i] az i fokszámú fát fogja tartalmazni. KIEGYENLIT(S) for i:=1 to D(n) A[i]:=Nil for S minden w fájára x:=w; d:=x.fokszam; while (A[d]!=Nil) y:=A[d] /x-el egyez˝ o fokszámú csúcs if x.kulcs > y.kulcs then Csere(x,y) KupacotSzerkeszt(H,y,x); A[d]:=Nil; d:=d+1; 5
A[d]:=x; min(S):=Nil for i:=1 to D(n) if A[i]!=Nil then tegyük A[i]-t S gyökérlistájába if (min(S)=Nil) or (kulcs(A[i])< kulcs(min(S))) then min(S):=A[i] KupacotSzerkeszt(S,y,x) vegyük ki y-t S-b˝ ol tegyük y-t x egy fiává és növeljük x fokszámát megjelol(x):=Hamis; Muvelet ˝ költsége: A SorBol m˝uvelet amortizált költsége O(D(n)). Az egyesített gyökérlista mérete legfeljebb D(n) + t(S) − 1, így a tényleges költség O(D(n) + t(S)). A potenciál a minimális pont kivágása el˝ott t(S) + 2m(S), a KIEGYENLIT végrehajtása után D(n) + 1 + 2m(S). Tehát az amortizált költség O(D(n) + t(S)) + ((D(n) + 1) + 2m(S)) − (t(S) + 2m(S)) = O(D(n)) + O(t(S)) − t(S). Amely költség O(D(n)) nagyságrend˝u, ha a potenciálfüggvényt konstanszorosára növeljük úgy, hogy dominálja az O(t(S))-ben szerepl˝o konstanst. Kulcsot csökkent Az algoritmus kivágja az adott elemet, ha sérül a kupactulajdonság, továbbá a KASZKÁD-VÁGÁS algoritmus segítségével gondoskodik arról, hogy ne legyen olyan pont, ami több fiát is elveszti. KulcsotCsokkent(S,x,k) if k>kulcs(x) Then write "hibas adat" return kulcs(x):=k y:=apa(x) if y!=Nil and kulcs(x)
Amortizált költség: Legyen c azon csúcsok száma, amelyeket felhelyezünk a gyökérlistába. A KulcsotCsokkent eljárás tényleges költsége O(c). Vizsgáljuk a potenciál változását. Az új Fibonacci kupac gyökérlistájában c új csúcs szerepel, így a potenciálfüggvény els˝o része c-vel n˝o, másrészt a KASZKÁD-VÁGÁSOK során c-1 megjelölt csúcs jelöletlenné válik, és egy jelöletlen jelölté, így a második rész 2(c − 2)-vel csökken. Következésképpen a potenciál értéke c-4-el csökken. Így az amortizált költség konstans lesz, ha a potenciálfüggvényt konstansszorosára növeljük úgy, hogy dominálja az O(c) valós költségben szerepl˝o konstanst. AltTorol(S,x) Az algoritmus átállítja a törlend˝o elem kulcsát −∞-re majd a minimális elemet (amely az átállítást követ˝oen a törlend˝o elem kivágja). AltTorol(S,x) KulcsotCsokkent(S,x,-Inf) Torol(S) Az algoritmus futási ideje O(logn), mivel a felhasznált eljárásoké annyi.
7
