N12

12.

Egyesítheto˝ prioritási sor

É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 )

12.1.

Az EPrisor megvalósítása balos kupaccal

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

12.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 12.3. definíció. Az F bináris fa balos-fa, ha (∀p ∈ F)(rang(p) = rang(Jobb(p)) + 1) 12.4. következmény. Ha F balos-fa, akkor a jobb-sarkába vezeto˝ út a legrövidebb, levélhez vezeto˝ út. 12.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

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

F1

F2

x

α1

β1

y

α2

β2 x≥y

x
F y

α1

α2 E(β1, F2)

E(β2, F1)

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; 2

rangj = (jobbfa==null) ? 0 :jobbfa.rang; if (rangb
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.

Ahol F1 és F2 az egyesítendo˝ kupacok, F az egyesítés rész-eredménye. Transzformációs invariáns: 1. F1 , F2 és F kupac 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; 3

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){ 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; 4

} public E Elso(){ return (gyoker==null) ? null : gyoker.elem; } public void Torol(){ if (gyoker==null) return; eszam--; gyoker=NRFaEgyesit(gyoker.bal, gyoker.jobb); } }

5