9. gyakorlat
Szorgalmi beadandó:
- Bármilyen nyelv
- Tömb a max absztakció ami használható (Vec, HashMap már nem)
Kupac
Kupac = heap
- Szigorúan bináris fa: minden belső pontjának két gyereke van
- teljes bináris fa: olyan szigorúan bináris fa, ahol minden levél azonos szinten van
- majdnem teljes bináris fa: olyan teljes bináris fa, melynek legalsó (levél) szintjéről elhagytunk néhány levelet (de nem az összeset).
- majdnem teljes balra tömörített bináris fa: majdnem teljes bináris fa, de levelek csak a legalsó szintről, a jobb oldalról hiányozhatnak. Ezeket szintfolytonos fáknak is nevezzük.
- kupac: Maximum kupac: Egy majdnem teljes, balra tömörített bináris fa, melynek minden belső pontjára teljesül, hogy a belső pont kulcsa nagyobb vagy egyenlő a gyerekei kulcsánál, tehát a kupac tetején a legnagyobb elem található.
- Minimum kupac: same, but minimum
Mivel balra tömörített, ezért lehet tömbként reprezentáli:
Ha egy csúcs indexe \(i\), akkor:
- Bal gyerekének indexe: \(2i\)
- Jobb gyerekének indexe: \(2i+1\)
- Szülő indexe: \(\left\lfloor\frac{i}{2}\right\rfloor\)