A kupac

Mi a kupac?

A kupac legrövidebb megragadása a következő:

1. Egy véges sok elemből álló sokaságféle.
   Azonos típusú elemekből áll.
2. Az elemtípus rendezett.
   Létezik rajta értelmezett rendezési reláció: reflexív, antiszimmetrikus, tranzitív. (L. a wikin.)
3. a. Minden elemnek legfeljebb két közvetlen rákövetkezője és legfeljebb egy megelőzője van.
   b. Egyetlen elemnek nincs megelőzője.
   
   III° ⇒ a kupac tekinthető bináris fának is!
   
   
4. Minden eleme kisebb vagy egyenlő a közvetlen rákövetkezőinél, ha van(nak) ilyen(ek).
   
   II° + IV° ⇒ a kupac részben rendezett elemekből álló sokaságot jelent.
   
   
5. Építve a III° következményére:
   a. szintenként teljes (azaz az n. szinten 2^n-1 darab elem van, n=1,2,...),
   b. kivéve –esetleg– a legalsó, n. szintet (az n+1. szinten már 0 darab elem van), amely balról folytonos kitöltöttségű.
   
   V° ⇒ (szokatlan módon) megköti az ábrázolást.

A fentieket nevezzük összefoglalóan kupac-tulajdonságnak.

1. ábra: Az ábrázolt konkrét adatszerkezetre ellenőrizze
a fenti feltételek teljesülését!

Következmények:

1. Minden elem kisebb vagy egyenlő az összes rákövetkezőjénél.
   II° (tranzitivitás) + IV° ⇒ A°
   De az azonos szinten levő elemek között nincs elvárt rendezettség!
2. Az első, a gyökér elem a legkisebb (nincs nála kisebb a sokaságban).
   A° + II° (tranzitivitás) ⇒ B°
3. Ábrázolható folytonos memória területen, pl. a tömbben.
   V° (a: szintenkénti teljesség + b: balról folytonosság) ⇒ C°

2. ábra: Az 1. ábrán látható konkrét adatszerkezet
V° szerinti elhelyezkedése a memóriában.

A következmények már előre sejtetik az alábbi műveletek némelyikének értelmét, majdani hasznát, sőt az ábrázolás „logikáját” is.
A kupacot mint adatszerkezetet, típuskonstrukciós eszközt így definiáljuk:

ExportModul Kupac(Típus TElem):
  Eljárás
   Üres(Változó k:Kupac)
  Függvény
   ÜresE(Konstans k:Kupac):Logikai
   Első(Konstans k:Kupac):TElem
   Index(Konstans k:Kupac, e:TElem):Egész  [„index” → tömbben ábrázolás]
  Eljárás
   Módosít(Változó k:Kupac, Konstans i:Egész, e:TElem)   [i: „index” → tömbben ábrázolás]
   Felcsúsztat(Változó k:Kupac, Konstans i:Egész)        [i: „index” → tömbben ábrázolás]
   Lecsúsztat(Változó k:Kupac, Konstans i:Egész)         [i: „index” → tömbben ábrázolás]
  Függvény
   Kupacból(Változó k:Kupac):TElem
  Eljárás
   Kupacba(Változó k:Kupac, Konstans e:TElem)
  Függvény
   HibásE(Változó k:Kupac):Logikai
Modul vége.  

A Kupacból és a Kupacba műveletek a kupac-tulajdonságot megtartó műveletek. A Módosít viszont az érték helyben történő megváltoztatása révén elronthatja a rendezettséget, így negatívan hathat a kupac-tulajdonságra. Ennek visszaállítását célozzák a „csúsztató” műveletek.

Az elemek közvetlen elérését lehetővé tevő Index és Módosít művelet a tömbbel való rokonságot jelzi.

A kupac megvalósítása

A kupac hatékony működésének feltétele egy speciális folytonos ábrázolás: egy speciális tömbre visszavezetés.
A specialitást az elemek logikai egymásutánisága jelenti.

3. ábra: Az 1. ábrán látható konkrét adatszerkezet
V° szerinti elhelyezkedése egy tömben.

A bináris fákkal való szoros kapcsolat megengedi, hogy az alábbi nevű indexelő függvényeket, ill. rendezési függvényt használjuk.
Ezek megkönnyítik a kupac bináris faként való kezelését!
Alább vázoljuk egy lehetséges ábrázolását, egyelőre „hagyományosan”, rekordként, és az ábrázoláshoz igazítjuk annak kezelő műveleteit.

Konstans
  MaxN:Egész(???)
Típus
  Kupac=Rekord( n:Egész,
                ke:Tömb(1..MaxN:TElem),
                hiba:Logikai )
  [indexelő függvények:]
  Függvény BalGyerek(Konstans k:Kupac,i:Egész):Egész
    BalGyerek:=2*i
  Függvény vége. 
  Függvény JobbGyerek(Konstans k:Kupac,i:Egész):Egész
    JobbGyerek:=2*i+1
  Függvény vége. 
  Függvény Szülő(Konstans k:Kupac,i:Egész):Egész
    Szülő:=i Div 2
  Függvény vége. 
  Függvény UtsóGyerek(Konstans k:Kupac):Egész
    UtsóGyerek:=k.n
  Függvény vége.
  [rendező függvény:]
  Függvény KisebbikGyereke(Konstans k:Kupac,s:Egész):Egész
    [Ef: 2≤2*s≤k.n, azaz 's' szülőnek van gyereke]
    Változó
      b,j:Egész
    b:=BalGyerek(k,s); j:=JobbGyerek(k,s)  
    Ha j>UtsóGyerek(k) [jobboldali gyereke nincs]
       vagy k.ke(b)<TElemk.ke(j) [a baloldali kisebb] akkor
      KisebbikGyereke:=b
    különben
      KisebbikGyereke:=j
    Elágazás vége
  Függvény vége. 

A fenti műveletek mindegyikéhez megfogalmazhatók előfeltételek, de mivel „belterjesek” (azaz nem exportáljuk) a helyes használatukban biztosak vagyunk, ezért nem ellenőrizzük teljesülésüket.

Térjünk vissza a kupac teljes megvalósításához! A kupac modulja az alábbi:

Modul Kupac(Típus TElem):

  Reprezentáció
  
    Konstans
      MaxN:Egész(???)
    Típus
      KupacElemek=Tömb(1..MaxN:TElem)
    Változó [ez az, amit feljebb Kupac típusként (rekordként) definiáltunk]
      n:Egész
      ke:KupacElemek
      hiba:Logikai
      
  Implementáció
  
    [segéd műveletek: --------------------------------------------------]
    Függvény BalGyerek(Konstans k:Kupac,i:Egész):Egész
    … [l. fentebb]
    Függvény JobbGyerek(Konstans k:Kupac,i:Egész):Egész
    … [l. fentebb]
    Függvény Szülő(Konstans k:Kupac,i:Egész):Egész
    … [l. fentebb]
    Függvény UtsóGyerek(Konstans k:Kupac):Egész
    … [l. fentebb]
    Függvény KisebbikGyereke(Konstans k:Kupac,s:Egész):Egész
    … [l. fentebb]
    
    [típus-műveletek: --------------------------------------------------]
    Eljárás Üres(Változó k:Kupac):
      n:=0; hiba:=Hamis
    Eljárás vége. 
    
    Függvény ÜresE(Konstans k:Kupac):Logikai
      ÜresE:=n=0
    Függvény vége. 
    
    Függvény Első(Konstans k:Kupac):TElem
      [Ef: n>0]
      Első:=ke(1)
    Függvény vége.
    
    Függvény Index(Konstans k:Kupac,e:TElem):Egész
      [Uf: e∈ke → Index(k,e)=i ∧ ke(i)=e
           e∉ke → Index(k,e)=0]
      Változó
        i:Egész
      i:=1
      Ciklus amíg i≤n és ke(i)≠e
        i:+1
      Ciklus vége
      Ha i≤n akkor  Index:=i
           különben Index:=0
    Függvény vége.
    
    Eljárás  Módosít(Változó k:Kupac, Konstans i:Egész,e:TElem):
      [Ef: n>0 ∧ i∈[1..n]]
      ke(i):=e
    Eljárás vége.
    …

Az alábbi műveletek elvégzésénél ügyelünk a kupac-tulajdonság fennmaradására!

    …
    [kupac-tulajdonságot helyreállító eljárások: -----------------------]
    Eljárás  Felcsúsztat(Változó k:Kupac, Konstans i:Egész):
      [Ef: n>0 ∧ i∈[1..n]]
      Ha i>1 [nem gyökérelem] akkor
        Ha ke(i)<ke(Szülő(k,i)) [nem teljesül II°] akkor
          Csere(ke(i),ke(Szülő(k,i)))[Csere(x,y) ≡ s:=x; x:=y; y:=s]
          Felcsúsztat(k,Szülő(k,i))
        Elágazás vége
      Elágazás vége
    Eljárás vége. 
    
    Eljárás  Lecsúsztat(Változó k:Kupac, Konstans i:Egész):
      [Ef: n>0 ∧ i∈[1..n]]
      Változó
        g:Egész
      Ha BalGyerek(k,i)≤UtsóGyerek(k) [i.-nek van gyereke] akkor 
        g:=KisebbikGyereke(k,i)
        Ha ke(i)>ke(g) [nem teljesül II°] akkor
          Csere(ke(i),ke(g))
          Lecsúsztat(k,g)
        Elágazás vége
      Elágazás vége
    Eljárás vége.
    
    [kupac-tulajdonságot megtartó műveletek: ----------------------------]
    Függvény Kupacból(Változó k:Kupac):TElem
      [Ef: n>0]
      Kupacból:=ke(1)  [az elsőt, a legkisebbet kivesszük]
      ke(1):=ke(n)     [a szintfolytonosság megtartása érdekében: az utolsót előre tesszük]
      n:-1             [már eggyel kevesebb eleme van]
      [ha nem vált üressé a kupac,
       a rendezettség szempontjából esetleg rossz helyre került első elemet a helyére csúsztatjuk:]
      Ha n>0 akkor Lecsúsztat(k,1)    
    Függvény vége. 
    
    Eljárás  Kupacba(Változó k:Kupac, Konstans e:TElem):
      [Ef: n<MaxN]
      n:+1             [eggyel több eleme lesz]
      ke(n):=e         [a szintfolytonosság megtartása érdekében: a végére tesszük az új elemet]
      [a rendezettség szempontjából esetleg rossz helyre került utolsó elemet a helyére csúsztatjuk:]
      Felcsúsztat(k,n) [az új elemet a helyére tesszük]
    Eljárás vége. 
    …

És végül:

    …
    Függvény  HibásE(Változó k:Kupac):Logikai
      HibásE:=hiba; hiba:=Hamis
    Függvény vége.
     
  Inicializálás
    n:=0; hiba:=Hamis
    
Modul vége. 

1. feladat:

Készítse el a fenti modul Pascal object-alapú unitját, amelyben az elemtípus a String! Felhasználhatja az alábbi félig kész keretet:
http://people.inf.elte.hu/szlavi/AlgAdat/1felev/Kupac/StrKupac_Unit_keret.pas .
Szüksége lehet az Általános rutinokat tartalmazó inklúdra, töltse le'

Írjon hozzá egy próbaprogramot, amely legalább az alábbi szituációkban való helyes működését ellenőrzi:

• Üres kupac állapota az elvárt.
• Egy üres állapotú kupac első elemét nem lehet kiolvasni: a kupac hibássá válik.
• A hibás kupacot a HibásE függvény helyesen kezeli.
• Tegyen bele a kupacba nagyság szerint mindenféle helyre illő elemet, és ellenőrizze, hogy jó helyre került-e.
• Vegye ki a kupacból az elemeket, miközben ellenőrzi az állapotváltozását! Jusson el az üres kupacig, és még abból is próbáljon elemet kivenni! Ellenőrizze a hibásságot!

Ilyesmire gondolhat: http://people.inf.elte.hu/szlavi/AlgAdat/1felev/Kupac/KupacProba.exe . Töltse le és futassa!

2. feladat:

Fogalmazza meg, milyen célt szolgálnak a „csúsztató” műveletek!

Íme…
Amikor egy elem értéke (a többiekhez „viszonyitott” rendezettsége) megváltozik, akkor kell alkalmazni a „csúsztató” eljárásokat,
hogy a kupac-tulajdonság ismét helyre álljon!

3. feladat:

Remélem, hiányérzete támadt! Ha Ön is úgy érzi, hogy a kupac „nyelvezetéből” hiányzik az alábbi:
Függvény Érték(Konstans k:Kupac, i:Egész):TElem
függvény, tegye bele a modulba és a megvalósított unitba is!

4. feladat:

Készítse el a kupac unitjából –a szokásos módon– az inklúdálható class-alapú változatot (OKupac_Sablon.Inc)! Legyen az ábrázolásban szereplő tömb maximális méretét jelentő MaxN a kupac-sablon „import paramétere”!
A próba programot is igazítsa hozzá (OKupac_Inc_Proba.pas)! Ne feledje: a kupacot létre is kell hozni a használat előtt (nem elég üressé tenni)!

5. feladat:

Készítse el a kupac class-alapú változatot, amelyet a OKupac_Sablon_Unit.pas) unitba csomagol!
Írjon egy próba programot is (OKupac_Sablon_Proba.pas)! Ne feledje: a kupacot létre is kell hozni a használat előtt (nem elég üressé tenni)!
Felhasználhatja az alábbi félig kész keretet:
http://people.inf.elte.hu/szlavi/AlgAdat/1felev/Kupac/OKupac_Sablon_Unit_keret.pas .

Kupac rendezés

A kupacot hatékonyan fel lehet használni rendezésre.

Ötlet:

1. A kupacba egyenként beletesszük az elemeket a bemeneti (rendezetlen) sorozatból
   – ez, N elem esetén, O(N·log₂N) műveletigényű felépítést jelent.
   Ennek során a kupacban előre került a „leg” (l. a B° következményt).
2. Kivesszük a kupac elejéről a „leg”-et, és betesszük a kimeneti, rendezett sorozatba
   – ez O(log₂N) műveletigényű lépés.
   A kivétel során előre került a következő „leg”.
3. Összesen N-szer kell elvégezni az előbbi lépést, az elemkivételt,
   – így az össz műveletigény O(N·log₂N).

Az algoritmus:

Az algoritmust animálva töltse le: pdf, mp4!

Konstans
  MaxN:Egész(???)
Típus
  TElemek=Tömb(1..MaxN:TElem)
  
Eljárás Rendez(Változó X:TElemek, Konstans N:Egész):
  Változó
    K:Kupac(TElem)
  Üres(K)
  Ciklus i=1-től N-ig
    Kupacba(K,X(i))
  Ciklus vége
  Ciklus i=1-től N-ig
    X(i):=Kupacból(K)
  Ciklus vége
Eljárás vége.

Pihenésül…

… hallgassa és nézze a rendezési algoritmusokról a következő tanulságos kis videókat:
15 Sorting Algorithms in 6 Minutes,
Visualization and Comparison of Sorting Algorithms.

1. A kupac fenti modulját felhasználva készítse el a prioritási sor modulját!
   

   ExportModul TPrSor(TElem):
     Eljárás  Üres[legyen](Változó s:TPrSor)
     Függvény ÜresE(Konstans s:TPrSor):Logikai
     Eljárás  Sorba(Változó s:TPrSor, Konstans e:TElem)
     Függvény Sorból(Változó s:TPrSor):TElem 
              Első(Változó s:TPrSor):TElem 
              Hossz(Konstans s:TPrSor):Egész 
              TeleE(Konstans s:TPrSor):Logikai 
              HibásE(Változó s:TPrSor):Logikai
   Modul vége.

   A TElem típust modulként „csomagolja”! Legalább ezeket a műveleteket valósítsa meg:
   

   ExportModul TElem:
     Eljárás  Write(Konstans elő:Szöveg, e:TElem, utó:Szöveg)
              Read(Konstans kérdés:Szöveg, Változó e:TElem)
     Operátor KisebbE(Konstans e1,e2:TElem):Logikai
              Másként e1<e2
   Modul vége.

2. A kupac object- vagy class-alapon megvalósított unitját felhasználva készítse el a prioritási sor unitját!
   Természetesen adjon egy, unitot próbára tevő programot is!
   Ötletek…
   
   1. A TElem típushoz kell tartozzon egy rendezési reláció. A TElem típust valósítsa meg unittal! Ezt hozzá kell fordítani a TPrSor modulhoz.
      
   2. A TPrSor-ban a TElem-re vonatkozó < relációt (rendezési operátort) logikai értékű függvényként implementáltuk.
      Implementálhatja „valódi” bináris, infix operátorként is. Ennek FP-beli megvalósításának azonban utána kell néznie. (Nagyon úgy tűnik –a dokumentáció nem szól róla–, hogy operátorként nem megy!
3. Adott egy személyi adatokat (soronként) tartalmazó szöveges adatfájl. Az egyes mezőket válassza el a "|" jel! Fájlból beolvasva egy kupacba, rendezze az adatokat valamely adott mezője (pl. vezeték+keresztnév) szerint! A rendezett adatokat egy másik fájlba írja ki!
   Felteheti, hogy egy-egy személyi adat belefér egy Stringbe (hossz≤255 byte). Így kiindulhat az előbb készült String-elemű kupac unitból.
   Ugye világos a legfőbb probléma?
   
   1. Az összefüggő string-elem mezőkre bontása. Érdemes egy konverziós függvénypárt írni:
      TElem→String és String→TElem, ahol TElem=Record vnev,knev,...:String End.
   2. A rendezési reláció nem az egész elemen, hanem annak csak egy részén van értelmezve, ezért újra kell írnia a KisebbikGyereke rendezési relációt megvalósító függvényt.