streamalism.org

1. Úvod

V tomto tutoriále uvidíme, ako funguje Heap Sort, a implementujeme ho v Jave.

Heap Sort je založené na dátovej štruktúre Heap. Aby sme správne pochopili triedenie haldy, najskôr sa pozrieme na haldy a na to, ako sú implementované.

2. Hromadná dátová štruktúra

Hromada je a špecializovaná stromová dátová štruktúra. Preto sa skladá z uzlov. Priradíme prvky uzlom: každý uzol obsahuje presne jeden prvok.

Uzly tiež môžu mať deti. Ak uzol nemá žiadne deti, hovoríme mu list.

To, čo Heap robí špeciálnym, sú dve veci:

1. hodnota každého uzla musí byť menšie alebo rovnaké ako všetky hodnoty uložené v jej podradených položkách
2. je to kompletný strom, čo znamená, že má najmenšiu možnú výšku

Z dôvodu prvého pravidla najmenej prvkov bude vždy v koreňovom adresári stromu.

To, ako presadzujeme tieto pravidlá, závisí od implementácie.

Hromady sa zvyčajne používajú na implementáciu prioritných frontov, pretože halda je veľmi efektívna implementácia extrakcie najmenšieho (alebo najväčšieho) prvku.

2.1. Haldy varianty

Halda má veľa variantov, všetky sa líšia v niektorých detailoch implementácie.

Napríklad to, čo sme opísali vyššie, je a Min. Halda, pretože rodič je vždy menší ako všetky jeho deti. Prípadne by sme mohli definovať Max-Heap, v takom prípade je rodič vždy väčší ako jeho deti. Preto bude najväčší prvok v koreňovom uzle.

Môžeme si vybrať z mnohých implementácií stromu. Najpriamejší je Binárny strom. V binárnom strome môže mať každý uzol najviac dve deti. Voláme ich ľavé dieťa a správne dieťa.

Najjednoduchší spôsob, ako presadiť druhé pravidlo, je použitie úplného binárneho stromu. Celý binárny strom dodržiava niekoľko jednoduchých pravidiel:

1. ak má uzol iba jedno dieťa, malo by to byť jeho ľavé dieťa
2. iba najpravejší uzol na najhlbšej úrovni môže mať presne jedno dieťa
3. listy môžu byť iba na najhlbšej úrovni

Pozrime sa na tieto pravidlá s niekoľkými príkladmi:

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

Stromy 1, 2, 4, 5 a 7 sa riadia pravidlami.

Strom 3 a 6 porušuje 1. pravidlo, 8 a 9 druhé pravidlo a 10 porušuje 3. pravidlo.

V tomto návode zameriame sa na Min-Heap s binárnym stromom implementácia.

2.2. Vkladanie prvkov

Mali by sme implementovať všetky operácie tak, aby sme udržali haldy invarianty. Týmto spôsobom môžeme stavajte haldu opakovaným vkladaním, takže sa zameriame na operáciu jednoduchého vloženia.

Element môžeme vložiť pomocou nasledujúcich krokov:

1. vytvorte nový list, ktorý je najpravdepodobnejším miestom na najhlbšej úrovni, a uložte položku do tohto uzla
2. ak je prvok menší ako jeho rodič, zameníme ich
3. pokračujte krokom 2, kým prvok nebude menší ako jeho rodič, alebo kým sa nestane novým koreňom

Upozorňujeme, že krok 2 neporuší pravidlo haldy, pretože ak nahradíme hodnotu uzla menšou, bude stále menšia ako jej potomkovia.

Pozrime sa na príklad! Chceme vložiť 4 do tejto haldy:

 2 / \ / \ 3 6 / \ 5 7

Prvým krokom je vytvorenie nového listu, ktorý obsahuje 4:

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

Pretože 4 je menej ako jej rodič, 6, zameníme ich:

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

Teraz skontrolujeme, či je 4 menšia ako jej rodič alebo nie. Keďže jeho rodič je 2, zastavujeme. Halda stále platí a vložili sme číslo 4.

Vložme 1:

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

Musíme vymeniť 1 a 4:

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

Teraz by sme mali vymeniť 1 a 2:

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

Pretože 1 je nový koreň, zastavili sme.

3. Implementácia haldy v Jave

Keďže používame a Plný binárny strom, môžeme ho implementovať pomocou poľa: prvok v poli bude uzol v strome. Každý uzol označíme indexmi poľa zľava doprava, zhora nadol nasledujúcim spôsobom:

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

Jediná vec, ktorú potrebujeme, je sledovať, koľko prvkov uložíme do stromu. Týmto spôsobom bude indexom nasledujúceho prvku, ktorý chceme vložiť, veľkosť poľa.

Pomocou tohto indexovania môžeme vypočítať index nadradeného a podriadeného uzla:

• rodič: (index - 1) / 2
• ľavé dieťa: 2 * index + 1
• správne dieťa: 2 * index + 2

Pretože sa nechceme obťažovať prerozdelením polí, implementáciu ešte viac zjednodušíme a použijeme znak ArrayList.

Základná implementácia binárneho stromu vyzerá takto:

trieda BinaryTree {List elements = new ArrayList (); void add (E e) {elements.add (e); } boolean isEmpty () {return elements.isEmpty (); } E elementAt (int index) {návrat elements.get (index); } int parentIndex (int index) {return (index - 1) / 2; } int leftChildIndex (int index) {návrat 2 * index + 1; } int rightChildIndex (int index) {návrat 2 * index + 2; }}

Vyššie uvedený kód iba pridá nový prvok na koniec stromu. Preto musíme v prípade potreby prejsť novým prvkom nahor. Môžeme to urobiť pomocou nasledujúceho kódu:

trieda halda {// ... void add (E e) {elements.add (e); int elementIndex = elements.size () - 1; while (! isRoot (elementIndex) &&! isCorrectChild (elementIndex)) {int parentIndex = parentIndex (elementIndex); swap (elementIndex, parentIndex); elementIndex = parentIndex; }} boolean isRoot (int index) {return index == 0; } boolean isCorrectChild (int index) {return isCorrect (parentIndex (index), index); } 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 (); } void swap (int index1, int index2) {E element1 = elementAt (index1); E element2 = elementAt (index2); elements.set (index1, element2); elements.set (index2, element1); } // ...}

Upozorňujeme, že keďže musíme prvky porovnávať, je potrebné ich implementovať java.util. Porovnateľné.

4. Hromadné triedenie

Pretože koreň haldy vždy obsahuje najmenší prvok, Myšlienka Heap Sort je celkom jednoduchá: odstráňte koreňový uzol, kým sa halda nevyprázdni.

Jediná vec, ktorú potrebujeme, je operácia odstránenia, ktorá haldu udrží v konzistentnom stave. Musíme zabezpečiť, aby sme neporušili štruktúru binárneho stromu alebo vlastnosti haldy.

Aby sme zachovali štruktúru, nemôžeme vymazať žiadny prvok okrem listu úplne vpravo. Ide teda o odstránenie prvku z koreňového uzla a uloženie listu úplne vpravo v koreňovom uzle.

Ale táto operácia s najväčšou pravdepodobnosťou naruší vlastnosť Heap. Takže ak je nový koreň väčší ako ktorýkoľvek z jeho podradených uzlov, zameníme ho za jeho najmenej podriadený uzol. Pretože najmenší podriadený uzol je menší ako všetky ostatné podradené uzly, neporušuje to vlastnosť Heap.

Stále zamieňame, kým sa element nestane listom, alebo kým nebude menší ako všetky jeho deti.

Odstráňte koreň z tohto stromu:

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

Najskôr položíme posledný list do koreňa:

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

Pretože je potom väčší ako obe jeho deti, zameníme ho za jeho najmenšie dieťa, ktoré je 2:

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

4 je menej ako 6, takže zastavujeme.

5. Implementácia haldy triedenia v Jave

Všetko, čo máme, odstránenie koreňa (praskanie) vyzerá takto:

trieda halda {// ... E pop () {if (isEmpty ()) {throw new IllegalStateException ("You cannot pop from an empty heap"); } E vysledok = elementAt (0); int lasElementIndex = elements.size () - 1; swap (0, lasElementIndex); elements.remove (lasElementIndex); int elementIndex = 0; while (! isLeaf (elementIndex) &&! isCorrectParent (elementIndex)) {int smallerChildIndex = smallerChildIndex (elementIndex); swap (elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } vrátiť výsledok; } boolean isLeaf (int index) {return! isValidIndex (leftChildIndex (index)); } boolean isCorrectParent (int index) {return isCorrect (index, leftChildIndex (index)) && isCorrect (index, rightChildIndex (index)); } int smallerChildIndex (int index) {int leftChildIndex = leftChildIndex (index); int rightChildIndex = rightChildIndex (index); if (! isValidIndex (rightChildIndex)) {return leftChildIndex; } if (elementAt (leftChildIndex) .compareTo (elementAt (rightChildIndex)) <0) {return leftChildIndex; } návrat rightChildIndex; } // ...}

Ako sme už povedali, triedením sa iba vytvára halda a opakovane sa odstraňuje root:

trieda halda {// ... statické  Zoznamové zoradenie (Iterovateľné prvky) {Heap heap = of (elements); Výsledok zoznamu = nový ArrayList (); while (! heap.isEmpty ()) {result.add (heap.pop ()); } vrátiť výsledok; } statický  Halda (Iterovateľné prvky) {výsledok haldy = nová halda (); pre (E element: elements) {result.add (element); } vrátiť výsledok; } // ...}

Pomocou nasledujúceho testu môžeme overiť jeho funkčnosť:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList () {// dané prvky List = Arrays.asList (3, 5, 1, 4, 2); // keď List seřazenéElementy = Heap.sort (prvky); // potom assertThat (orderedElements) .isEqualTo (Arrays.asList (1, 2, 3, 4, 5)); }

Poznač si to mohli by sme poskytnúť implementáciu, ktorá bude usporiadaná na mieste, čo znamená, že poskytujeme výsledok v rovnakom poli, v ktorom sme dostali prvky. Týmto spôsobom navyše nepotrebujeme žiadne prechodné pridelenie pamäte. Táto implementácia by však bola o niečo ťažšie pochopiteľná.

6. Časová zložitosť

Halda sa skladá z dva kľúčové kroky, vkladanie prvok a odstránenie koreňový uzol. Oba kroky majú zložitosť O (log n).

Pretože oba kroky opakujeme n-krát, celková zložitosť triedenia je O (n log n).

Upozorňujeme, že sme nezmieňali náklady na prerozdelenie polí, ale keďže to tak je O (n), neovplyvňuje to celkovú zložitosť. Ako sme už spomenuli, je tiež možné implementovať triedenie na mieste, čo znamená, že nie je potrebné žiadne nové pridelenie poľa.

Za zmienku tiež stojí, že 50% prvkov sú listy a 75% prvkov sú na dvoch najspodnejších úrovniach. Väčšina operácií vkladania preto nebude trvať viac ako dva kroky.

Upozorňujeme, že v prípade údajov z reálneho sveta je program Quicksort zvyčajne výkonnejší ako program Heap Sort. Strieborná podšívka je, že Heap Sort má vždy najhorší prípad O (n log n) časová zložitosť.

7. Záver

V tomto tutoriáli sme videli implementáciu Binary Heap a Heap Sort.

Aj keď je to časová zložitosť je O (n log n), vo väčšine prípadov nejde o najlepší algoritmus na základe údajov z reálneho sveta.

Ako obvykle sú príklady k dispozícii na GitHub.