Hogyan "rendeződik" egy kupac?
Ugye a kupac az egy balra zárt bináris fa. A feladat az, hogy alakítsuk maximális kupaccá... Az ugye gondolom azt jelenti, hogy a gyökérelem legyen a legnagyobb érték és minden szülő nagyobb legyen, mint a gyerekei.
Tehát például a [6,3,0,2,5,1,4]-ből (ahol ugye 6 a gyökér, gyerekei 3 (annak 2 és 5) és 0 (annak pedig 1 és 4), hogyan lesz [0,1,2,3,4,5,6].
Az nem világos, hogy egy bináris fa maximum rendezése az hogyan zajlik. Például: fogja az utolsó levélelemet, rájön, hogy nagyobb, mint a szülője megcseréli (gondolom ezzel az algoritmusnak nincs vége, ezt addig csinálja, amíg el nem jut az első olyan elemig, ami kisebb, vagy el nem jut a gyökérelem helyére)... Ez eddig oké. Utána mi történik? Ugrik egyet a "vizsgált elem a tömbben és az utolsó előtti elemmel is lefut ugyanez az algoritmus? Csak mert én ezt kipróbáltam és nem rendezte úgy a tömböt, ahogy akartam.
Illetve még annyit, hogy a heap sort és a maximális kupaccá alakítás az ugyanaz?
(Igen, fogalmatlan vagyok, de plíz mellőzzük az anyámat)
válasza:Na kicsit segítek a fogalmakkal, de túl nagy lenne a terjedelme, hogy kifejtsem teljesen. Utána kell majd olvasnod, de biztosan nagyon sok anyag van ebben a témában a neten. Elég alap struktúra.
Szóval jól mondod. A kupac az egy olyan balra rendezett bináris fa ahol a szülő nem-kisebb a gyerekeknél. Ezt viszont jellemzően nem bináris faként ábrázolják hanem egy tömbként ahol sorfolytonosan jönnek az elemek. Így az jön ki, hogy az x. elem gyerekei 2*x+1 és 2*x+2 (ha 0-tól megy az index).
A kupaccá alakítás az az a folyamat amikor egy random rendezettlen tömböt ilyen tulajdonságúvá alakítasz az elemek megfelelő cserélgetésével.
A headsort meg két fázisból áll. Az első amikor kupaccá alakítja.
Majd kiveszi a legelső elemet, helyreállítja a kupac tulajdonságot, majd az épp felszabadult helyre rakja. Ezt ismétli ameddig a kupac el nem fogy.
válasza:A kupac a bináris fa egyik fajtája.
Kupacot általában nem szokás rendezni. Nem véletlenül van úgy, ahogy.
Ha mégis rendezni kivánsz egy kupacot, akkor a legegyszerűbb, ha egy másik bináris fát építesz belőle.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!