5.4. Kupac

Egy teljes bináris fát kupacnak tekintjük, ha erre a fára teljesül a kupac tulajdonság: egy tetszőleges csúcs eleme nem lehet nagyobb a fiaiban levő elemeknél.

5.4.1. Kupacépítés

A bináris fa egy eleme és annak leszármazottjai egy részfát határoznak meg, melynek a gyökere az adott elem. Apák és fiaik elemeinek cseréjével elérjük, hogy egyre nagyobb és nagyobb részfákban teljesüljön a kupac tulajdonság. A csak levélből álló részfára természetesen egyből teljesül a kupac-tulajdonság. Ezért a tömb utolsó elemétől az első irányába haladva a következőket hajtjuk végre: ha A[j] ≥ min(A[2j],A[2j + 1]), akkor apa és a kisebbik értékű fia elemei helyet cserélnek, majd rekurzívan hívjuk meg a KUPAC eljárást a szóban forgó fiúra. A haladási irány miatt eredetileg a fiúkra teljesült a kupac tulajdonság. Ez a cserével esetleg felborult, ezért ezt az adott fiúnál újra meg kell vizsgálni.

Procedure KUPAC-ÉPÍTő(A) 
Input: Az A számtömb 
Eredmény: Az A tömb kupac tulajdonságú 
1 for i = floor(A.hossz/2) downto 1 do 
2   KUPAC(A,i)

Procedure KUPAC(A,i) 
Input: Az A számtömb, i index 
Eredmény: Az A[i] gyökerű részfa kupac tulajdonságú 
1  b = 2i; 
2  j = 2i + 1; 
3  if b ≤= A.hossz and A[b] ≤ A[i] then 
4     k = b 
5  else 
6     k = i;
7  endif 
8  if j ≤= A.hossz and A[j] ≤ A[k] then 
9     k = j;
10 endif 
11 if k != i then 
12    A[i] és A[k] cseréje; 
13    KUPAC(A,k) 
14 endif

Hosszas számolások után belátható az a meglepő tény, hogy a kupacépítés, azaz egy tetszőleges tömb kupaccá alakítása lineáris bonyolultságú, melynek bizonyítása megtalálható Knuth könyvében [3, 171.o].

5.3. példa - 6. példa

Lássuk, hogyan építhető kupac a 11, 6, 5, 2, 1, 4, 3, 8, 7, 9 és 10 elemeket tartalmazó tömből! A könnyebb követhetőség érdekében ábrázoljuk a tömböt fával (1. ábra)!

5.1. ábra - 1. ábra

1. ábra


A KUPAC-ÉPÍTőeljárás alapján, mivel 11 elem van a tömbben, elsőként az ötödik elemet kell összehasonlítani a tizedikkel és tizenegyedikkel. Az ötödik a legkisebb, ezért nem változik semmi (2. ábra).

5.2. ábra - 2. ábra

2. ábra


Ezután a negyediket kell összeha sonlítani a nyolcadikkal és kilencedikkel, s a felső elem újra kisebb a többieknél (3. ábra).

5.3. ábra - 3. ábra

3. ábra


Majd a harmadikat kell összehasonlítani a hatodikkal és hetedikkel (4. ábra).

5.4. ábra - 4. ábra

4. ábra


A három szám közül a 3 a legkisebb, ezért ez kerül fel a harmadik helyre. Az itt található 5-öt a hetedik elem gyökerű kupacban kell elhelyezni, de mivel ez a fa csak a gyökérből áll, végeredményben a 3 és 5 helyet cserél. A soron következő lépésnél az 1 és a 6 cserél helyet (5. ábra).

5.5. ábra - 5. ábra

5. ábra


Majd ellenőrizni kell, hogy a 6 valóban a helyére került-e. Mivel kisebb mint a 9, illetve a 10, ezért már nem kell tovább mozgatni (6. ábra).

5.6. ábra - 6. ábra

6. ábra


Ezután folytathatjuk a fa vizsgálatát az első elemnél, s az 1 és 11 helyet cserél (7. ábra).

5.7. ábra - 7. ábra

7. ábra


A 11 még nem került a helyére, mert van olyan fia (mindkettő ilyen), mely nála kisebb. Ezért kicseréljük a kisebbikkel (8. ábra).

5.8. ábra - 8. ábra

8. ábra


A 11 még mindig nem került a helyére, így újabb csere következik (9. ábra).

5.9. ábra - 9. ábra

9. ábra


De most már minden a helyén van, tehát elkészült a kupac (10. ábra).

5.10. ábra - 10. ábra

10. ábra



5.4.2. Kupacrendezés

A kupac-tulajdonság miatt a gyökérhez tartozó eleme a legkisebb. Ezt az elemet a kupacból törölve, helyére a tömb utolsó elemét írva, s a tömböt újra kupaccá rendezve megkaphatjuk a tömb következő elemét. Ezt módszert újra és újra végrehajtva sorra megkapjuk a tömb elemeit rendezve (esetünkben csökkenő sorrendben). Ezt nevezzük kupacrendezésnek. A kupacrendezés O(n ln(n)) bonyolultságú. A törölt elemek külön helyen tárolása helyett tárolhatjuk az elemeket a tömb törlés miatt felszabadult helyein.

Procedure KUPAC-RENDEZÉS(A) 
Input: Az A számtömb 
Eredmény: A tömböt csökkenő sorrendbe rendezi 
1 KUPAC-ÉPÍTő(A) 
2 n = A.hossz; 
3 for i = n downto 2 do 
4    A[1] és A[i] cseréje; 
5    A.hossz = A.hossz − 1; 
6    KUPAC(A,1); 
7 endfor 
8 A.hossz = n;

A kupac.htm állomány tartalmazza azt a programot, amely egy véletlen módon generált számsorozatra végrehajtja a kupacrendezést. A program pirossal jelzi az apát és a két fiát, s kékkel a már rendezett számokat.