streamalism.org

1. Introduktion

I denne vejledning ser vi, hvordan Heap Sort fungerer, og vi implementerer det i Java.

Heap Sort er baseret på Heap-datastrukturen. For at forstå Heap Sort korrekt graver vi først i Heaps og hvordan de implementeres.

2. Heap-datastruktur

En bunke er en specialiseret træbaseret datastruktur. Derfor er den sammensat af noder. Vi tildeler elementerne til noder: hver node indeholder nøjagtigt et element.

Også noder kan have børn. Hvis en knude ikke har nogen børn, kalder vi det blad.

Hvad Heap gør specielt er to ting:

1. hver knudes værdi skal være mindre eller lig med alle værdier, der er gemt i dets børn
2. Det er en komplet træ, hvilket betyder, at den har den mindst mulige højde

På grund af den første regel, det mindste element vil altid være i roden af ​​træet.

Hvordan vi håndhæver disse regler er implementeringsafhængig.

Heaps bruges normalt til at implementere prioritetskøer, fordi Heap er en meget effektiv implementering af udpakning af det mindste (eller største) element.

2.1. Heap Varianter

Heap har mange varianter, som alle afviger i nogle implementeringsoplysninger.

For eksempel er det, vi har beskrevet ovenfor, en Min-Heap, fordi en forælder altid er mindre end alle sine børn. Alternativt kunne vi have defineret Max-Heap, i hvilket tilfælde en forælder altid er større end sine børn. Derfor vil det største element være i rodnoden.

Vi kan vælge imellem mange træimplementeringer. Det mest ligefremme er et binært træ. I et binært træ kan hver knudepunkt højst have to børn. Vi kalder dem venstre barn og højre barn.

Den nemmeste måde at håndhæve den 2. regel på er at bruge et fuldt binært træ. Et fuldt binært træ følger nogle enkle regler:

1. hvis en knude kun har ét barn, skal det være dets venstre barn
2. kun den længste knude på det dybeste niveau kan have nøjagtigt et barn
3. blade kan kun være på det dybeste niveau

Lad os se disse regler med nogle eksempler:

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

Træerne 1, 2, 4, 5 og 7 følger reglerne.

Træ 3 ​​og 6 overtræder 1. regel, 8 og 9 2. regel og 10 overtræder 3. regel.

I denne vejledning vi fokuserer på Min-Heap med et binært træ implementering.

2.2. Indsættelse af elementer

Vi skal gennemføre alle operationer på en måde, der holder bunken uforanderlige. På denne måde kan vi opbyg bunken med gentagne indsættelser, så vi fokuserer på operationen med enkelt indsats.

Vi kan indsætte et element med følgende trin:

1. Opret et nyt blad, der er den længst til rådighed tilgængelige plads på det dybeste niveau, og gem elementet i den node
2. hvis elementet er mindre end dets forælder, bytter vi dem
3. fortsæt med trin 2, indtil elementet er mindre end dets overordnede, eller det bliver den nye rod

Bemærk, at trin 2 ikke overtræder Heap-reglen, for hvis vi erstatter en nodes værdi med en mindre, vil den stadig være mindre end dens børn.

Lad os se et eksempel! Vi vil indsætte 4 i denne bunke:

 2 / \ / \ 3 6 / \ 5 7

Det første trin er at oprette et nyt blad, der gemmer 4:

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

Da 4 er mindre end forælder 6, bytter vi dem:

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

Nu kontrollerer vi, om 4 er mindre, end det er forælder eller ej. Da forældrene er 2, stopper vi. Bunken er stadig gyldig, og vi indsatte nummer 4.

Lad os indsætte 1:

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

Vi er nødt til at bytte 1 og 4:

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

Nu skal vi bytte 1 og 2:

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

Da 1 er den nye rod, stopper vi.

3. Bunkeimplementering i Java

Da vi bruger en Fuldt binært træ, vi kan implementere det med en matrix: et element i arrayet vil være en node i træet. Vi markerer hver knude med matrixindekserne fra venstre mod højre, fra top til bund på følgende måde:

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

Det eneste, vi har brug for, er at holde styr på, hvor mange elementer vi gemmer i træet. På denne måde vil indekset for det næste element, vi vil indsætte, være størrelsen på arrayet.

Ved hjælp af denne indeksering kan vi beregne indekset over forælder- og barneknudepunkterne:

• forælder: (indeks - 1) / 2
• venstre barn: 2 * indeks + 1
• højre barn: 2 * indeks + 2

Da vi ikke ønsker at gider med array-allokering, forenkler vi implementeringen endnu mere og bruger en ArrayList.

En grundlæggende implementering af binært træ ser sådan ud:

klasse BinaryTree {Listeelementer = ny ArrayList (); ugyldig tilføjelse (E e) {elements.add (e); } boolsk isEmpty () {return elements.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; }}

Koden ovenfor tilføjer kun det nye element til slutningen af ​​træet. Derfor er vi nødt til at krydse det nye element op, hvis det er nødvendigt. Vi kan gøre det med følgende kode:

klasse bunke {// ... ugyldig tilføj (E e) {elements.add (e); int elementIndex = elements.size () - 1; mens (! isRoot (elementIndex) &&! isCorrectChild (elementIndex)) {int parentIndex = parentIndex (elementIndex); swap (elementIndex, parentIndex); elementIndex = parentIndex; }} boolsk isRoot (int-indeks) {returindeks == 0; } boolsk isCorrectChild (int-indeks) {return isCorrect (parentIndex (index), index); } boolean isCorrect (int parentIndex, int childIndex) {if (! isValidIndex (parentIndex) ||! isValidIndex (childIndex)) {return true; } returner elementAt (parentIndex) .compareTo (elementAt (childIndex)) <0; } boolsk isValidIndex (int-indeks) {returindeks <elements.size (); } ugyldig swap (int index1, int index2) {E element1 = elementAt (index1); E element2 = elementAt (index2); elements.set (index1, element2); elements.set (index2, element1); } // ...}

Bemærk, at da vi skal sammenligne elementerne, skal de implementeres java.util.Comparable.

4. Heap Sort

Da roden af ​​bunken altid indeholder det mindste element, ideen bag Heap Sort er ret enkel: fjern rodnoden, indtil Heapen bliver tom.

Det eneste, vi har brug for, er en fjernoperation, der holder bunken i en konsistent tilstand. Vi skal sikre, at vi ikke krænker strukturen i det binære træ eller Heap-ejendommen.

For at bevare strukturen kan vi ikke slette noget element undtagen bladet til højre. Så ideen er at fjerne elementet fra rodnoden og gemme bladet til højre i rodnoden.

Men denne operation vil helt sikkert krænke Heap-ejendommen. Så hvis den nye rod er større end nogen af ​​dens underordnede noder, bytter vi den med dens mindste undernode. Da den mindste underordnede node er mindre end alle andre underordnede noder, overtræder den ikke egenskaben Heap.

Vi fortsætter med at bytte, indtil elementet bliver et blad, eller det er mindre end alle dets børn.

Lad os slette roden fra dette træ:

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

Først placerer vi det sidste blad i roden:

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

Da det er større end begge dets børn, bytter vi det med sit mindste barn, hvilket er 2:

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

4 er mindre end 6, så vi stopper.

5. Heap Sort Implementation i Java

Med alt, hvad vi har, ser rodfjerning (popping) sådan ud:

klasse bunke {// ... E pop () {if (isEmpty ()) {throw new IllegalStateException ("Du kan ikke pope fra en tom bunke"); } E resultat = elementAt (0); int lasElementIndex = elements.size () - 1; swap (0, lasElementIndex); elements.remove (lasElementIndex); int elementIndex = 0; mens (! isLeaf (elementIndex) &&! isCorrectParent (elementIndex)) {int smallerChildIndex = smallerChildIndex (elementIndex); swap (elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } returnere resultat } boolsk isLeaf (int-indeks) {return! isValidIndex (leftChildIndex (index)); } boolsk isCorrectParent (int index) {return isCorrect (index, leftChildIndex (index)) && isCorrect (index, rightChildIndex (index)); } int smallerChildIndex (int index) {int leftChildIndex = leftChildIndex (index); int rightChildIndex = rightChildIndex (indeks); hvis (! isValidIndex (rightChildIndex)) {return leftChildIndex; } hvis (elementAt (leftChildIndex) .compareTo (elementAt (rightChildIndex)) <0) {return leftChildIndex; } returner rightChildIndex; } // ...}

Som vi sagde før, er sortering bare at oprette en bunke og fjerne roden gentagne gange:

klasse bunke {// ... statisk  Listesortering (Iterable elements) {Heap heap = of (elements); Listeresultat = ny ArrayList (); mens (! heap.isEmpty ()) {result.add (heap.pop ()); } returnere resultat } statisk  Heap of (Iterable elements) {Heap result = new Heap (); for (E element: elements) {result.add (element); } returnere resultat } // ...}

Vi kan kontrollere, at det fungerer med følgende test:

@Test ugyldigt givenNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList () {// given listeelementer = Arrays.asList (3, 5, 1, 4, 2); // når List sortedElements = Heap.sort (elementer); // derefter assertThat (sortedElements) .isEqualTo (Arrays.asList (1, 2, 3, 4, 5)); }

Noter det vi kunne give en implementering, der sorterer på stedet, hvilket betyder, at vi leverer resultatet i samme array, som vi fik elementerne. Derudover har vi ikke brug for nogen mellemliggende hukommelsestildeling på denne måde. Imidlertid ville implementeringen være lidt sværere at forstå.

6. Tidskompleksitet

Heap slags består af to vigtige trin, indsættelse et element og fjernelse rodnoden. Begge trin har kompleksiteten O (log n).

Da vi gentager begge trin n gange, er den samlede sorteringskompleksitet O (n log n).

Bemærk, at vi ikke nævnte omkostningerne ved array-allokering, men da det er På), det påvirker ikke den samlede kompleksitet. Som vi nævnte før er det også muligt at implementere en sortering på stedet, hvilket betyder, at ingen arrayallokering er nødvendig.

Det er også værd at nævne, at 50% af elementerne er blade, og 75% af elementerne er på de to nederste niveauer. Derfor tager de fleste indsætningsoperationer ikke mere end to trin.

Bemærk, at på virkelige data er Quicksort normalt mere performant end Heap Sort. Sølvforingen er, at Heap Sort altid har en worst-case O (n log n) tidskompleksitet.

7. Konklusion

I denne vejledning så vi en implementering af Binary Heap og Heap Sort.

Selvom det er tidskompleksitet O (n log n), i de fleste tilfælde er det ikke den bedste algoritme på data fra den virkelige verden.

Som sædvanligt er eksemplerne tilgængelige på GitHub.