kupacrendezés
Tehát fokozatosan halad egy többé-kevésbé egyszerű, bonyolult, de hatékony módszer. Kupacrendezés az első ilyen módszerek, amelynek teljesítménye értékelik, mint az O (n log n).
Ennek előzménye, hogy a fő módszer, nézzük fordított rendezési opciót. A folyosón, ahelyett, hogy beillesztik a legkisebb eleme a bal végén a tömb, akkor válassza ki a legnagyobb elem, de kész építeni szekvenciát a jobb oldalon van.
Példa akció a tömb egy [0]. a [7]:
Függőleges vonal jelzi a bal széle már rendezve (jobb) oldalán a tömb.
Tekintsük a becslés a műveletek száma részletesen.
Összesen elvégzett n lépéseket, amelyek mindegyike áll kiválasztja a legnagyobb eleme egy szekvenciáját [0] .. egy [I] és az azt követő cseréje. Kiválasztási bekövetkezik brute force elemek olyan sorrendben, így a kívánt idő rajta: O (n). Tehát, n lépéseket O (n) minden egyes - ez O (N 2).
Azt, hogy javulást: építeni egy adatstruktúrát, amely lehetővé teszi, hogy válassza ki a maximális szekvencia elem nem O (n), és az O (logn) időt. Ezután a teljes teljesítmény válogatás n * O (logn) = O (n log n).
Ez a struktúra lehetővé kell tennie, hogy gyorsan helyezze be az új elemet (gyorsan építeni az eredeti tömb), és távolítsa el a legmagasabb elem (ez kerül egy részében a tömb már rendezve van - a jobb végén).
Így nevezzük a piramis (Heap) bináris magasságú fa k, ahol
- minden csomópont mélysége k vagy k-1 - kiegyensúlyozott fa.
- ahol a szint k-1 teljesen megtelik, és a K-szintek tele balról jobbra, azaz piramis alakú közelítőleg az alábbi formában:
- fut „piramis vagyon” minden elem kisebb vagy egyenlő, mint a szülő.
Hogyan kell tárolni a piramis? A legkevésbé problémás -, hogy azt egy tömbbe.
Közötti konzisztencia geometriai szerkezete, mint a fa és a piramis tömb beállítása a következőképpen:
- egy [0] tárolják fa gyökér
- bal és jobb a gyermekek az elem egy [I] tárolja sootvetstvennno egy [2i + 1], és egy [2i + 2]
Így egy tömb, amely tárolja a piramis, a következő jellemző: a [i]> = a [2i + 1], és a [i]> = a [2i + 2].
Előnye ennek a boltban piramisok nyilvánvalóak:
- további változók csak meg kell érteniük az áramkört.
- csomópontok tárolják felülről lefelé, szintenként.
- egyszintű csomópontok vannak tárolva a tömb balról jobbra.
Írunk a piramis, fent látható tömbként. Balról jobbra, fentről lefelé: 94 67 18 44 55 12 06 42. ábra helye piramis elem a tömb jelölt a jobb tetején.
Visszaszerez piramis a tömb, mint egy geometriai objektumot könnyen - tanú a tároló áramkör és felhívni a gyökértől kezdve.
1. fázis válogatás: az épület egy piramis
Root piramis építési lehet egy [K]. egy [n], k = [size / 2]. Ez része a tömb megfelel a tulajdonság piramis, mivel nincs indexek i, j: i = 2i + 1 (vagy j = 2i + 2). Csak azért, mert az ilyen i, j kívül tömb határokat.
Meg kell jegyezni, hogy ez a baj, hogy azt mondják, hogy a [k] .. a [n] egy piramis önálló tömb. Ez általánosságban nem igaz: ez lehet bármilyen elemekkel. Piramis ingatlan megmarad csak a forrás, a fő tömb [0]. egy [n].
Ezután fogjuk bővíteni a részét a tömb, amelynek egy ilyen hasznos funkció, hozzátéve, az egyik elem egy lépésben. A következő elem az egyes hozzátéve lépés - az egyik, hogy előtt áll az elkészült alkatrész.
Ahhoz, hozzátéve elem megmarad piramis, használjuk a következő eljárásnak expanziós piramis egy [i + 1] .. egy [n], hogy egy elem a [i], hogy a bal oldalon:
- Nézzük a fiai a bal és jobb - a tömb egy [2i + 1] és a [2i + 2] és válassza ki a legnagyobb közülük.
- Ha ez az elem nem több, mint egy [i] - változtassa meg a [i] helyen, és ugorjon a 2. lépésre, utalva az új helyzetben a [i] a tömb. Ellenkező esetben a az eljárás végén.
Új elem „árnyékolt” keresztül a piramis.
Tekintettel arra, hogy a magassága a piramis h <= log n, downheap требует O(log n) времени. Полный код процедуры построения пирамиды будет иметь вид:
Az alábbiakban a szemléltetés kedvéért adjuk a folyamat a piramis 8 és elemek:
A geometriai értelmezése a kulcsokat a kezdeti szegmens egy [size / 2]. egy [n] a levelek egy bináris fa, az alábbiak szerint. Egyenként a többi elemek mozognak a helyére, és így - amíg az egész piramis épül.
Az alábbi ábra az összeállítási folyamat. Felkészületlen a piramis (az elején a tömb) festett fehér színű, kielégítő ingatlan piramis végén a tömb - a sötétben.
2. fázis: a tényleges rendezési
Tehát a feladat az épület a piramisok a tömb sikeresen megoldotta. Amint látható, a tulajdonságok a piramis, a gyökér elem mindig maximális. Ezért az algoritmus 2. fázis:
- Vegyük a felső tagja a piramis egy [0]. egy [n] (egy első tömb), és a változás az utolsó pozíciótól. Most a „elfelejti” erről elem és további tekintve egy tömb a [0]. egy [n-1]. Átalakítani, hogy a piramis egy új első elem kellően rostálni.
- Ismételje 1. lépést, amíg a feldolgozott részét a tömb csökkentjük egyetlen elem.
Nyilvánvaló, hogy a végén a tömb minden alkalommal megkapja a maximális eleme a jelenlegi piramis, így a jobb oldali fokozatosan válik egy rendezett.
Kód külső rendezési eljárások:
Mi a teljesítménye egy algoritmus?
Építőipari piramis O (n log n) műveleteket, és sokkal pontosabb becslést akár O (n) annak a ténynek köszönhető, hogy a tényleges futási downheap magasságától függ a piramis már kialakult.
A második fázis O (n log n) idő: O (n) idő alatt vesszük a maximális szitálás lép fel, és a korábbi utolsó elem. A módszer előnye az stabil: átlagos számát komló (n log n) / 2, és ettől való eltérés értéke viszonylag kicsi.
Kupacrendezés több memóriát igényel.
A módszer nem stabil: a tömb a repülni, mint „felrázza”, hogy az eredeti sorrendet az elemek változhat véletlenszerűen.
Természetellenes viselkedés: részleges sorrendjét a tömb nem veszik figyelembe.