streamalism.org

1. Inleiding

In deze tutorial zullen we zien hoe Heap Sort werkt, en we zullen het in Java implementeren.

Heap Sort is gebaseerd op de Heap-gegevensstructuur. Om Heap Sort goed te begrijpen, zullen we eerst ingaan op Heaps en hoe deze worden geïmplementeerd.

2. Heap-gegevensstructuur

Een hoop is een gespecialiseerde boomgebaseerde datastructuur. Daarom is het samengesteld uit knooppunten. We kennen de elementen toe aan knooppunten: elk knooppunt bevat precies één element.

Ook kunnen knooppunten kinderen hebben. Als een knoop geen kinderen heeft, noemen we het blad.

Wat Heap speciaal maakt, zijn twee dingen:

1. de waarde van elk knooppunt moet zijn minder of gelijk aan alle waarden die zijn opgeslagen in de onderliggende items
2. het is een complete boom, wat betekent dat het de laagst mogelijke hoogte heeft

Vanwege de eerste regel, het minste element zal altijd in de wortel van de boom zitten.

Hoe we deze regels handhaven, is afhankelijk van de implementatie.

Heaps worden meestal gebruikt om prioriteitswachtrijen te implementeren, omdat Heap een zeer efficiënte implementatie is van het extraheren van het kleinste (of grootste) element.

2.1. Heap-varianten

Heap heeft veel varianten, die allemaal verschillen in sommige implementatiedetails.

Wat we hierboven hebben beschreven, is bijvoorbeeld een Min-Heap, omdat een ouder altijd minder is dan al zijn kinderen. Als alternatief hadden we Max-Heap kunnen definiëren, in welk geval een ouder altijd groter is dan zijn kinderen. Daarom bevindt het grootste element zich in het hoofdknooppunt.

We kunnen kiezen uit vele boomimplementaties. De meest eenvoudige is een binaire boom. In een binaire structuur kan elk knooppunt maximaal twee kinderen hebben. We bellen ze links kind en juiste kind.

De eenvoudigste manier om de tweede regel af te dwingen, is door een volledige binaire structuur te gebruiken. Een volledige binaire boom volgt enkele eenvoudige regels:

1. als een knoop slechts één kind heeft, zou dat het linkerkind moeten zijn
2. alleen het meest rechtse knooppunt op het diepste niveau kan precies één kind hebben
3. bladeren kunnen alleen op het diepste niveau zijn

Laten we deze regels eens bekijken met enkele voorbeelden:

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

De bomen 1, 2, 4, 5 en 7 volgen de regels.

Boom 3 en 6 schenden de 1e regel, 8 en 9 de 2e regel en 10 schenden de 3e regel.

In deze tutorial we zullen ons concentreren op Min-Heap met een binaire boom implementatie.

2.2. Elementen invoegen

We moeten alle bewerkingen op een manier implementeren die de Heap-invarianten houdt. Op deze manier kunnen we bouw de hoop op met herhaalde invoegingen, dus we zullen ons concentreren op de enkele invoegbewerking.

We kunnen een element invoegen met de volgende stappen:

1. maak een nieuw blad dat het meest rechtse beschikbare vak op het diepste niveau is en bewaar het item in dat knooppunt
2. als het element kleiner is dan het bovenliggende element, wisselen we ze om
3. ga verder met stap 2, totdat het element kleiner is dan zijn ouder of het de nieuwe wortel wordt

Merk op dat stap 2 de Heap-regel niet schendt, want als we de waarde van een knooppunt vervangen door een kleinere, zal deze nog steeds minder zijn dan de onderliggende waarden.

Laten we een voorbeeld bekijken! We willen 4 invoegen in deze Heap:

 2 / \ / \ 3 6 / \ 5 7

De eerste stap is om een ​​nieuw blad te maken waarin 4 wordt opgeslagen:

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

Omdat 4 minder is dan de ouder, 6, wisselen we ze om:

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

Nu kijken we of 4 kleiner is dan de ouder of niet. Omdat de ouder 2 is, stoppen we. De Heap is nog steeds geldig en we hebben nummer 4 ingevoegd.

Laten we er 1 invoegen:

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

We moeten 1 en 4 omwisselen:

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

Nu moeten we 1 en 2 verwisselen:

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

Aangezien 1 de nieuwe wortel is, stoppen we.

3. Heap-implementatie in Java

Omdat we een Volledige binaire structuur, we kunnen het implementeren met een array: een element in de array wordt een knooppunt in de boomstructuur. We markeren elk knooppunt met de array-indices van links naar rechts, van boven naar beneden op de volgende manier:

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

Het enige dat we nodig hebben, is bijhouden hoeveel elementen we in de boom opslaan. Op deze manier is de index van het volgende element dat we willen invoegen de grootte van de array.

Met behulp van deze indexering kunnen we de index van de bovenliggende en onderliggende knooppunten berekenen:

• ouder: (index - 1) / 2
• links kind: 2 * index + 1
• rechter kind: 2 * index + 2

Omdat we ons niet willen bezighouden met het opnieuw toewijzen van array's, zullen we de implementatie nog meer vereenvoudigen en een ArrayList.

Een eenvoudige Binary Tree-implementatie ziet er als volgt uit:

klasse BinaryTree {Lijstelementen = nieuwe ArrayList (); void add (E e) {elements.add (e); } boolean isEmpty () {retourelementen.isEmpty (); } E elementAt (int index) {return elements.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; }}

De bovenstaande code voegt alleen het nieuwe element toe aan het einde van de boomstructuur. Daarom moeten we het nieuwe element indien nodig naar boven verplaatsen. We kunnen het doen met de volgende code:

klasse Heap {// ... 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); } // ...}

Merk op dat aangezien we de elementen moeten vergelijken, ze geïmplementeerd moeten worden java.util.Comparable.

4. Heap sorteren

Omdat de root van de Heap altijd het kleinste element bevat, het idee achter Heap Sort is vrij simpel: verwijder de root node totdat de Heap leeg raakt.

Het enige dat we nodig hebben, is een verwijderingsbewerking, die de Heap in een consistente staat houdt. We moeten ervoor zorgen dat we de structuur van de binaire structuur of de eigenschap Heap niet schenden.

Om de structuur te behouden, kunnen we geen enkel element verwijderen, behalve het meest rechtse blad. Het idee is dus om het element uit de root-node te verwijderen en het meest rechtse blad in de root-node op te slaan.

Maar deze operatie zal zeker de Heap-eigenschap schenden. Zo als de nieuwe root groter is dan een van zijn onderliggende knooppunten, wisselen we deze met zijn kleinste onderliggende knooppunt. Omdat het kleinste onderliggende knooppunt kleiner is dan alle andere onderliggende knooppunten, schendt het de eigenschap Heap niet.

We blijven wisselen totdat het element een blad wordt, of het is minder dan al zijn kinderen.

Laten we de root uit deze boom verwijderen:

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

Eerst plaatsen we het laatste blad in de wortel:

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

Vervolgens, omdat het groter is dan zijn beide kinderen, ruilen we het met het kleinste kind, namelijk 2:

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

4 is minder dan 6, dus we stoppen.

5. Heap Sort-implementatie in Java

Met alles wat we hebben, ziet het verwijderen van de root (popping) er als volgt uit:

klasse Heap {// ... E pop () {if (isEmpty ()) {throw new IllegalStateException ("Je kunt niet uit een lege heap poppen"); } E resultaat = elementAt (0); int lasElementIndex = elements.size () - 1; swap (0, lasElementIndex); elements.remove (lasElementIndex); int elementIndex = 0; while (! isLeaf (elementIndex) &&! isCorrectParent (elementIndex)) {int smallChildIndex = smallChildIndex (elementIndex); swap (elementIndex, smallChildIndex); elementIndex = smallChildIndex; } resultaat teruggeven; } boolean isLeaf (int index) {return! isValidIndex (leftChildIndex (index)); } boolean isCorrectParent (int index) {return isCorrect (index, leftChildIndex (index)) && isCorrect (index, rightChildIndex (index)); } int smallChildIndex (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; } // ...}

Zoals we al eerder zeiden, sorteren is gewoon een heap maken en de root herhaaldelijk verwijderen:

klasse Heap {// ... statisch  Lijst sorteren (herhaalbare elementen) {Heap heap = of (elementen); Lijstresultaat = nieuwe ArrayList (); while (! heap.isEmpty ()) {resultaat.add (heap.pop ()); } resultaat teruggeven; } statisch  Heap van (herhaalbare elementen) {Heap-resultaat = nieuwe Heap (); for (E element: elements) {result.add (element); } resultaat teruggeven; } // ...}

We kunnen verifiëren dat het werkt met de volgende test:

@Test void givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList () {// gegeven lijstelementen = Arrays.asList (3, 5, 1, 4, 2); // wanneer Lijst gesorteerdeElements = Heap.sort (elementen); // vervolgens assertThat (gesorteerdeElements) .isEqualTo (Arrays.asList (1, 2, 3, 4, 5)); }

Let daar op we zouden een implementatie kunnen bieden, die op zijn plaats wordt gesorteerd, wat betekent dat we het resultaat in dezelfde array leveren als waarin we de elementen hebben gekregen. Bovendien hebben we op deze manier geen tussentijdse geheugentoewijzing nodig. Die implementatie zou echter een beetje moeilijker te begrijpen zijn.

6. Tijdscomplexiteit

Heap-sortering bestaat uit twee belangrijke stappen, invoegen een element en Verwijderen het hoofdknooppunt. Beide stappen hebben de complexiteit O (logboek n).

Omdat we beide stappen n keer herhalen, is de algehele sorteercomplexiteit O (n log n).

Merk op dat we de kosten van het opnieuw toewijzen van een array niet hebben genoemd, maar omdat het Aan), heeft het geen invloed op de algehele complexiteit. Zoals we eerder al zeiden, is het ook mogelijk om een ​​in-place sortering te implementeren, wat betekent dat er geen array-herverdeling nodig is.

Het is ook vermeldenswaard dat 50% van de elementen bladeren zijn en 75% van de elementen zich op de twee onderste niveaus bevinden. Daarom duren de meeste invoegbewerkingen niet meer dan twee stappen.

Merk op dat Quicksort bij gegevens uit de echte wereld doorgaans beter presteert dan Heap Sort. De zilveren voering is dat Heap Sort altijd een worst-case heeft O (n log n) tijd complexiteit.

7. Conclusie

In deze tutorial zagen we een implementatie van Binary Heap en Heap Sort.

Ook al is het tijdcomplexiteit O (n log n), in de meeste gevallen is dit niet het beste algoritme voor gegevens uit de echte wereld.

Zoals gewoonlijk zijn de voorbeelden beschikbaar op GitHub.