streamalism.org

1. Bemutatkozás

Ebben az oktatóanyagban megnézzük, hogyan működik a Heap Sort, és megvalósítjuk Java-ban.

A Heap Sort a Heap adatstruktúrán alapul. A Heap Sort megfelelő megértése érdekében először átkutatjuk a Heaps-t és azok megvalósítását.

2. Halom adatszerkezet

Egy kupac a speciális faalapú adatszerkezet. Ezért csomópontokból áll. Az elemeket csomópontokhoz rendeljük: minden csomópont pontosan egy elemet tartalmaz.

A csomópontoknak gyermekeik is lehetnek. Ha egy csomópontnak nincs gyermeke, levélnek hívjuk.

Amit Heap különlegessé tesz, az két dolog:

1. minden csomópont értékének meg kell lennie kisebb vagy egyenlő a gyermekeiben tárolt összes értékkel
2. ez egy teljes fa, ami azt jelenti, hogy a lehető legkisebb magasságú

Az első szabály miatt a legkevesebb elem mindig a fa gyökerében lesz.

Az, hogy miként érvényesítjük ezeket a szabályokat, a megvalósítástól függ.

A halmokat általában a prioritási sorok megvalósítására használják, mert a Heap a legkevesebb (vagy legnagyobb) elem kibontásának nagyon hatékony megvalósítása.

2.1. Halomváltozatok

A kupacnak sok változata van, mindegyik különbözik a megvalósítás egyes részleteiben.

Például az, amit fent leírtunk, a Min-Heap, mert a szülő mindig kevesebb, mint az összes gyermeke. Alternatív megoldásként meghatározhatnánk a Max-Heap-t is, ebben az esetben a szülő mindig nagyobb, mint a gyermeke. Ezért a legnagyobb elem a gyökércsomópontban lesz.

Számos fa megvalósítás közül választhatunk. A legegyenesebb egy bináris fa. A bináris fában minden csomópontnak legfeljebb két gyermeke lehet. Mi hívjuk őket bal gyermek és helyes gyerek.

A 2. szabály érvényesítésének legegyszerűbb módja a Teljes bináris fa használata. A teljes bináris fa néhány egyszerű szabályt követ:

1. ha egy csomópontnak csak egy gyermeke van, akkor annak legyen a bal gyermeke
2. csak a legmélyebb szinten lévő jobb szélső csomópontnak lehet pontosan egy gyermeke
3. levelek csak a legmélyebb szinten lehetnek

Lássuk ezeket a szabályokat néhány példával:

 1 2 3 4 5 6 7 8 9 10 () () () () () () () () () () / \ / \ / \ / \ / \ / / / \ () () () () () () () () () () () () () () / \ / \ / \ / / \ () () () () () () () () () / ()

Az 1., 2., 4., 5. és 7. fák betartják a szabályokat.

A 3. és 6. fa megsérti az 1., a 8. és 9. a 2. szabályt, a 10. fa pedig a 3. szabályt.

Ebben az oktatóanyagban a Min-Heap-re koncentrálunk egy bináris fával végrehajtás.

2.2. Elemek beszúrása

Minden műveletet úgy kell végrehajtanunk, hogy az megtartsa a kupac invariánsokat. Így megtehetjük ismételt behelyezésekkel építsd meg a Halmot, ezért az egybetétes műveletre fogunk összpontosítani.

A következő lépésekkel helyezhetünk be egy elemet:

1. hozzon létre egy új levelet, amely a legmélyebb szinten rendelkezésre álló jobb szélső nyílás, és tárolja az elemet abban a csomópontban
2. ha az elem kevesebb, mint a szülője, akkor kicseréljük őket
3. folytassa a 2. lépéssel, amíg az elem kevesebb lesz, mint a szülője, vagy az új gyökérré válik

Ne feledje, hogy a 2. lépés nem sérti a kupac szabályt, mert ha egy csomópont értékét kisebbre cseréljük, akkor is kisebb lesz, mint a gyerekeké.

Lássunk egy példát! 4-et szeretnénk beszúrni ebbe a kupacba:

 2 / \ / \ 3 6 / \ 5 7

Az első lépés egy új levél létrehozása, amely 4-et tárol:

 2 / \ / \ 3 6 / \ / 5 7 4

Mivel 4 kisebb, mint a szülője, 6, cseréljük őket:

 2 / \ / \ 3 4 / \ / 5 7 6

Most ellenőrizzük, hogy a 4 kisebb-e, mint a szülője, vagy sem. Mivel a szülője 2, megállunk. A kupac továbbra is érvényes, és beillesztettük a 4-es számot.

Helyezzük be az 1-et:

 2 / \ / \ 3 4 / \ / \ 5 7 6 1

Fel kell cserélnünk 1-et és 4-et:

 2 / \ / \ 3 1 / \ / \ 5 7 6 4

Most fel kellene cserélnünk az 1-et és a 2-et:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

Mivel 1 az új gyökér, leállunk.

Heap implementáció Java-ban

Mivel használjuk a Teljes bináris fa, egy tömbdel implementálhatjuk: egy elem a tömbben a fa csomópontja lesz. Minden csomópontot a tömbindexekkel jelölünk balról jobbra, fentről lefelé a következő módon:

 0 / \ / \ 1 2 / \ / 3 4 5

Csak arra van szükségünk, hogy nyomon kövessük, hány elemet tárolunk a fában. Így a következő beilleszteni kívánt elem indexe a tömb nagysága lesz.

Ezen indexelés segítségével kiszámíthatjuk a szülő és gyermek csomópontok indexét:

• szülő: (index - 1) / 2
• bal gyermek: 2 * index + 1
• helyes gyerek: 2 * index + 2

Mivel nem akarunk tömbök átcsoportosításával bajlódni, még inkább leegyszerűsítjük a megvalósítást, és egy Tömb lista.

Az alapvető bináris fa megvalósítás így néz ki:

class BinaryTree {List elemek = new ArrayList (); void add (E e) {elemek.add (e); } logikai isEmpty () {return elements.isEmpty (); } E elemAt (int index) {return elemek.get (index); } int parentIndex (int index) {return (index - 1) / 2; } int leftChildIndex (int index) {return 2 * index + 1; } int rightChildIndex (int index) {return 2 * index + 2; }}

A fenti kód csak az új elemet adja hozzá a fa végéhez. Ezért szükség esetén felfelé kell haladnunk az új elemen. Megtehetjük a következő kóddal:

osztály Halom {// ... void add (E e) {elemek.add (e); int elementIndex = elements.size () - 1; while (! isRoot (elementIndex) &&! isCorrectChild (elementIndex)) {int parentIndex = parentIndex (elementIndex); csere (elementIndex, parentIndex); elementIndex = parentIndex; }} logikai isRoot (int index) {return index == 0; } logikai isCorrectChild (int index) {return isCorrect (parentIndex (index), index); } logikai isCorrect (int parentIndex, int childIndex) {if (! isValidIndex (parentIndex) ||! isValidIndex (childIndex)) {return true; } return elementAt (parentIndex) .compareTo (elementAt (childIndex)) <0; } logikai isValidIndex (int index) {return index <elemek.size (); } void swap (int index1, int index2) {E elem1 = elemAt (index1); E elem2 = elemAt (index2); elemek.készlet (index1, elem2); elements.set (index2, elem1); } // ...}

Ne feledje, hogy mivel össze kell hasonlítanunk az elemeket, azokat végre kell hajtaniuk java.util.Hasonlítható.

4. Halom rendezés

Mivel a Halom gyökere mindig a legkisebb elemet tartalmazza, a Heap Sort mögött rejlő ötlet meglehetősen egyszerű: távolítsa el a gyökércsomópontot, amíg a Heap kiürül.

Az egyetlen dolog, amire szükségünk van, egy eltávolítási művelet, amely a Halmot állandó állapotban tartja. Gondoskodnunk kell arról, hogy ne sértsük meg a bináris fa vagy a halom tulajdonságát.

A szerkezet megőrzése érdekében a jobb szélső levél kivételével egyetlen elemet sem törölhetünk. Az ötlet tehát az, hogy eltávolítsuk az elemet a gyökércsomópontból, és a jobb szélső levelet tároljuk a gyökércsomópontban.

De ez a művelet minden bizonnyal sérti a Halom tulajdonságait. Így ha az új gyökér nagyobb, mint bármelyik gyermekcsomópont, kicseréljük a legkisebb gyermekcsomópontjával. Mivel a legkisebb gyermekcsomópont kevesebb, mint az összes többi gyermekcsomópont, ez nem sérti a Halom tulajdonságot.

Addig cserélünk, amíg az elem levélké nem válik, vagy kevesebb lesz, mint az összes gyermeke.

Töröljük a gyökeret erről a fáról:

 1 / \ / \ 3 2 / \ / \ 5 7 6 4

Először az utolsó levelet tesszük a gyökérbe:

 4 / \ / \ 3 2 / \ / 5 7 6

Aztán, mivel nagyobb, mint mindkét gyermeke, kicseréljük a legkisebb gyermekével, ami 2:

 2 / \ / \ 3 4 / \ / 5 7 6

A 4 kevesebb, mint 6, ezért megállunk.

5. Halom rendezés megvalósítása Java-ban

A gyökér eltávolítása (popping) a következőképpen néz ki:

osztály Halom {// ... E pop () {if (isEmpty ()) {dobjon új IllegalStateException-t ("Nem lehet üres kupacból ugrani"); } E eredmény = elemAt (0); int lasElementIndex = elements.size () - 1; csere (0, lasElementIndex); elemek.remove (lasElementIndex); int elemIndex = 0; while (! isLeaf (elementIndex) &&! isCorrectParent (elementIndex)) {int kisebbChildIndex = kisebbChildIndex (elementIndex); swap (elemIndex, kisebbChildIndex); elementIndex = kisebbChildIndex; } visszatérési eredmény; } logikai isLeaf (int index) {return! isValidIndex (leftChildIndex (index)); } logikai isCorrectParent (int index) {return isCorrect (index, leftChildIndex (index)) && isCorrect (index, rightChildIndex (index)); } int kisebbChildIndex (int index) {int leftChildIndex = leftChildIndex (index); int rightChildIndex = rightChildIndex (index); if (! isValidIndex (rightChildIndex)) {return leftChildIndex; } if (elementAt (leftChildIndex) .compareTo (elementAt (rightChildIndex)) <0) {return leftChildIndex; } return rightChildIndex; } // ...}

Mint korábban mondtuk, a rendezés csak egy halom létrehozását jelenti, és a gyökér ismételt eltávolítását:

osztály Halom {// ... statikus  Lista rendezése (Iterálható elemek) {Heap heap = of (elemek); Lista eredménye = new ArrayList (); while (! heap.isEmpty ()) {result.add (heap.pop ()); } visszatérési eredmény; } statikus  Halom (iterálható elemek) {Halom eredménye = új Halom (); for (E elem: elemek) {eredmény.add (elem); } visszatérési eredmény; } // ...}

A következő teszt segítségével ellenőrizhetjük, hogy működik-e:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList () {// megadott Lista elemek = Tömbök.asList (3, 5, 1, 4, 2); // amikor a List sortedElements = Heap.sort (elements); // majd assertThat (sortedElements) .isEqualTo (Arrays.asList (1, 2, 3, 4, 5)); }

Vegye figyelembe, hogy olyan megvalósítást tudnánk biztosítani, amely helyben válogat, ami azt jelenti, hogy ugyanabban a tömbben adjuk meg az eredményt, mint az elemek. Ezen kívül így nincs szükség köztes memória-allokációra. Ezt a megvalósítást azonban kissé nehezebb megérteni.

6. Az idő komplexitása

A halomfajta áll két kulcsfontosságú lépés, beillesztés egy elem és eltávolítása a gyökércsomópont. Mindkét lépés összetett O (log n).

Mivel n lépést megismételjük mindkét lépést, az általános rendezési komplexitás az O (n log n).

Ne feledje, hogy nem említettük a tömb átcsoportosításának költségeit, de mivel ez van Tovább), ez nem befolyásolja az általános összetettséget. Továbbá, amint azt korábban említettük, lehetséges a hely szerinti rendezés megvalósítása, ami azt jelenti, hogy nincs szükség tömbök újraterjesztésére.

Érdemes megemlíteni azt is, hogy az elemek 50% -a levél, és az elemek 75% -a a két legalsó szinten található. Ezért a legtöbb beszúrási művelet két lépést nem igényel.

Ne feledje, hogy a valós adatok esetében a Quicksort általában jobban teljesít, mint a Heap Sort. Az ezüst bélés az, hogy a Heap Sortnak mindig van a legrosszabb esete O (n log n) az idő bonyolultsága.

7. Következtetés

Ebben az oktatóanyagban a bináris kupac és a kupac rendezés megvalósítását láthattuk.

Annak ellenére, hogy itt az idő, a komplexitás igen O (n log n), a legtöbb esetben nem ez a legjobb algoritmus a valós adatokon.

Szokás szerint a példák elérhetők a GitHub oldalon.