streamalism.org

1. Uvod

U ovom uputstvu vidjet ćemo kako funkcionira Heap Sort i implementirat ćemo ga u Javu.

Sortiranje hrpe temelji se na strukturi podataka Heap. Da bismo pravilno razumjeli sortiranje hrpe, prvo ćemo istražiti hrpe i kako se one primjenjuju.

2. Struktura podataka hrpe

Hrpa je specijalizirana struktura podataka zasnovana na stablu. Stoga se sastoji od čvorova. Elemente dodjeljujemo čvorovima: svaki čvor sadrži točno jedan element.

Također, čvorovi mogu imati djecu. Ako čvor nema djece, nazivamo ga list.

Ono što Heap čini posebnim su dvije stvari:

1. vrijednost svakog čvora mora biti manje ili jednako svim vrijednostima pohranjenim u njegovoj djeci
2. to je cjelovito stablo, što znači da ima najmanju moguću visinu

Zbog 1. pravila, najmanji element uvijek će biti u korijenu stabla.

Način provedbe ovih pravila ovisi o provedbi.

Gomile se obično koriste za implementaciju prioritetnih redova jer je Heap vrlo učinkovita implementacija izdvajanja najmanjeg (ili najvećeg) elementa.

2.1. Varijante hrpe

Hrpa ima mnogo varijanti, sve se razlikuju u nekim detaljima implementacije.

Na primjer, ono što smo gore opisali je a Min-Heap, jer je roditelj uvijek manji od sve njegove djece. Alternativno, mogli smo definirati Max-Heap, u tom je slučaju roditelj uvijek veći od djece. Stoga će najveći element biti u korijenskom čvoru.

Možemo birati između mnogih implementacija stabla. Najizravnije je Binarno stablo. U binarnom stablu svaki čvor može imati najviše dvoje djece. Mi ih zovemo lijevo dijete i pravo dijete.

Najlakši način za provođenje 2. pravila je korištenje punog binarnog stabla. Potpuno binarno stablo slijedi nekoliko jednostavnih pravila:

1. ako čvor ima samo jedno dijete, to bi trebalo biti njegovo lijevo dijete
2. samo krajnji desni čvor na najdubljoj razini može imati točno jedno dijete
3. lišće može biti samo na najdubljoj razini

Pogledajmo ova pravila s nekoliko primjera:

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

Drveće 1, 2, 4, 5 i 7 slijedi pravila.

Stablo 3 i 6 krše 1. pravilo, 8. i 9. 2. pravilo, a 10 krše 3. pravilo.

U ovom vodiču, usredotočit ćemo se na Min-Heap s binarnim stablom provedba.

2.2. Umetanje elemenata

Sve bismo operacije trebali implementirati na način koji zadržava Invarijante hrpe. Ovako, možemo izgraditi hrpu ponovljenim umetanjem, pa ćemo se usredotočiti na operaciju s jednim umetanjem.

Element možemo umetnuti u sljedećim koracima:

1. stvorite novi list koji je najdesniji dostupan utor na najdubljoj razini i pohranite predmet u taj čvor
2. ako je element manji od nadređenog, zamjenjujemo ih
3. nastavite s korakom 2, sve dok element ne bude manji od nadređenog ili postane novi korijen

Imajte na umu da taj korak 2 neće kršiti pravilo Heap, jer ako vrijednost čvora zamijenimo manjom, ona će i dalje biti manja od podređene.

Pogledajmo primjer! Želimo umetnuti 4 u ovu hrpu:

 2 / \ / \ 3 6 / \ 5 7

Prvi korak je stvaranje novog lista koji pohranjuje 4:

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

Budući da je 4 manje od nadređenog 6, mijenjamo ih:

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

Sada provjeravamo je li 4 manje od roditelja ili ne. Budući da mu je roditelj 2, zaustavljamo se. Hrpa i dalje vrijedi, a mi smo umetnuli broj 4.

Umetnimo 1:

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

Moramo zamijeniti 1 i 4:

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

Sada bismo trebali zamijeniti 1 i 2:

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

Budući da je 1 novi korijen, zaustavljamo se.

3. Implementacija hrpe u Javi

Budući da koristimo a Puno binarno stablo, možemo ga implementirati s nizom: element u polju bit će čvor u stablu. Svaki čvor označavamo indeksima polja slijeva udesno, od vrha do dna na sljedeći način:

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

Jedino što trebamo je pratiti koliko elemenata pohranjujemo u stablo. Na taj će način indeks sljedećeg elementa koji želimo umetnuti biti veličina polja.

Pomoću ovog indeksiranja možemo izračunati indeks nadređenih i podređenih čvorova:

• roditelj: (indeks - 1) / 2
• lijevo dijete: Indeks 2 * + 1
• pravo dijete: 2 * indeks + 2

Budući da se ne želimo zamarati preraspodjelom niza, još ćemo pojednostaviti implementaciju i upotrijebiti ArrayList.

Osnovna implementacija Binarnog stabla izgleda ovako:

klasa BinaryTree {Elementi popisa = novi ArrayList (); void add (E e) {elements.add (e); } boolean isEmpty () {return elements.isEmpty (); } E elementAt (int indeks) {return elements.get (index); } int parentIndex (int index) {return (indeks - 1) / 2; } int leftChildIndex (int indeks) {return 2 * index + 1; } int rightChildIndex (int indeks) {return 2 * index + 2; }}

Gornji kod samo dodaje novi element na kraj stabla. Stoga moramo novi element prevaliti prema gore ako je potrebno. To možemo učiniti sa sljedećim kodom:

razred Hrpa {// ... void add (E e) {elements.add (e); int elementIndex = elements.size () - 1; while (! isRoot (elementIndex) &&! isCorrectChild (elementIndex)) {int parentIndex = parentIndex (elementIndex); zamjena (elementIndex, parentIndex); elementIndex = nadređeni indeks; }} boolean isRoot (int index) {index povrata == 0; } boolean isCorrectChild (int indeks) {return isCorrect (nadređeni indeks (indeks), indeks); } boolean isCorrect (int parentIndex, int childIndex) {if (! isValidIndex (parentIndex) ||! isValidIndex (childIndex)) {return true; } return elementAt (parentIndex) .compareTo (elementAt (childIndex)) <0; } boolean isValidIndex (int index) {return index <elements.size (); } zamjena void (int index1, int index2) {E element1 = elementAt (index1); E element2 = elementAt (indeks2); elements.set (index1, element2); elements.set (index2, element1); } // ...}

Imajte na umu da, budući da moramo usporediti elemente, oni ih trebaju implementirati java.util.Uporedivo.

4. Razvrstavanje po hrpi

Budući da korijen Hrpe uvijek sadrži najmanji element, ideja koja stoji iza sortiranja hrpe prilično je jednostavna: uklonite korijenski čvor dok hrpa ne postane prazna.

Jedino što nam treba je operacija uklanjanja koja održava hrpu u dosljednom stanju. Moramo osigurati da ne kršimo strukturu Binarnog stabla ili svojstva Heap.

Da bismo zadržali strukturu, ne možemo izbrisati nijedan element, osim desnog lista. Dakle, ideja je ukloniti element iz korijenskog čvora i pohraniti krajnji desni list u korijenski čvor.

Ali ova će operacija sasvim sigurno prekršiti svojstvo Heap. Tako ako je novi korijen veći od bilo kojeg od njegovih podređenih čvorova, zamjenjujemo ga s najmanje podređenim čvorom. Budući da je najmanje podređenih čvorova manje od svih ostalih podređenih čvorova, to ne krši svojstvo Heap.

Zamjenjujemo se sve dok element ne postane list ili manje od sve njegove djece.

Izbrišimo korijen s ovog stabla:

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

Prvo stavimo zadnji list u korijen:

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

Zatim, budući da je veći od oba njegova djeteta, zamijenimo ga s najmanje dijete, a to je 2:

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

4 je manje od 6, pa stajemo.

5. Implementacija sortiranja hrpe u Javi

Uz sve što imamo, uklanjanje korijena (iskakanje) izgleda ovako:

razred Hrpa {// ... E pop () {if (isEmpty ()) {baciti novi IllegalStateException ("Ne možete iskočiti iz prazne hrpe"); } E rezultat = elementAt (0); int lasElementIndex = elements.size () - 1; zamijeni (0, lasElementIndex); elements.remove (lasElementIndex); int elementIndex = 0; while (! isLeaf (elementIndex) &&! isCorrectParent (elementIndex)) {int manjiChildIndex = manjiChildIndex (elementIndex); zamjena (elementIndex, manjiChildIndex); elementIndex = manjiChildIndex; } vratiti rezultat; } logički isLeaf (int indeks) {return! isValidIndex (leftChildIndex (indeks)); } boolean isCorrectParent (int index) {return isCorrect (index, leftChildIndex (index)) && isCorrect (index, rightChildIndex (index)); } int largerChildIndex (int indeks) {int leftChildIndex = leftChildIndex (indeks); int rightChildIndex = rightChildIndex (indeks); if (! isValidIndex (rightChildIndex)) {return leftChildIndex; } if (elementAt (leftChildIndex) .compareTo (elementAt (rightChildIndex)) <0) {return leftChildIndex; } return rightChildIndex; } // ...}

Kao što smo već rekli, sortiranje je samo stvaranje hrpe i višekratno uklanjanje korijena:

razred Hrpa { // ... statički  Razvrstavanje popisa (Iterable elements) {Heap heap = of (elements); Rezultat popisa = novi ArrayList (); while (! heap.isEmpty ()) {result.add (heap.pop ()); } vratiti rezultat; } statički  Hrpa (Iterable elements) {Rezultat hrpe = nova hrpa (); za (E element: elementi) {result.add (element); } vratiti rezultat; } // ...}

Sljedećim testom možemo provjeriti funkcionira li:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList () {// zadani elementi popisa = Arrays.asList (3, 5, 1, 4, 2); // kada je Lista sortedElements = Heap.sort (elementi); // zatim assertThat (sortedElements) .isEqualTo (Arrays.asList (1, 2, 3, 4, 5)); }

Imajte na umu, to mogli bismo pružiti implementaciju koja se sortira na mjestu, što znači da rezultat dajemo u istom nizu u kojem smo dobili i elemente. Uz to, na ovaj način ne treba nam nikakvo srednje dodjeljivanje memorije. Međutim, tu bi provedbu bilo malo teže razumjeti.

6. Složenost vremena

Vrsta hrpe sastoji se od dva ključna koraka, umetanje element i uklanjanje korijenski čvor. Oba koraka imaju složenost O (zapisnik n).

Budući da oba koraka ponavljamo n puta, ukupna složenost sortiranja je O (n zapisnik n).

Imajte na umu da nismo spomenuli troškove preraspodjele niza, ali budući da jesu Na), to ne utječe na ukupnu složenost. Također, kao što smo već spomenuli, moguće je implementirati sortiranje na mjestu, što znači da nije potrebno preraspodjeljivanje niza.

Također je vrijedno spomenuti da su 50% elemenata lišće, a 75% elemenata na dvije najniže razine. Stoga većina operacija umetanja neće trebati više od dva koraka.

Imajte na umu da je na stvarnim podacima Quicksort obično učinkovitiji od Heap Sort. Srebrna podstava je da Heap Sort uvijek ima najgori slučaj O (n zapisnik n) složenost vremena.

7. Zaključak

U ovom uputstvu vidjeli smo implementaciju Binarne hrpe i sortiranja hrpe.

Iako je vremenska složenost takva O (n zapisnik n), u većini slučajeva to nije najbolji algoritam za podatke iz stvarnog svijeta.

Kao i obično, primjeri su dostupni na GitHubu.