Haugsortering i Java

1. Introduksjon

I denne opplæringen ser vi hvordan Heap Sort fungerer, og vi implementerer det i Java.

Heap Sort er basert på Heap-datastrukturen. For å forstå Heap Sort riktig, vil vi først grave i Heaps og hvordan de implementeres.

2. Heap Datastruktur

En haug er en spesialisert trebasert datastruktur. Derfor består den av noder. Vi tilordner elementene til noder: hver node inneholder nøyaktig ett element.

Også noder kan få barn. Hvis en node ikke har noen barn, kaller vi det blad.

Det Heap gjør spesielt er to ting:

hver nodes verdi må være mindre eller lik alle verdiene som er lagret hos barna
det er en komplett tre, noe som betyr at den har minst mulig høyde

På grunn av den første regelen, det minste elementet vil alltid være i roten av treet.

Hvordan vi håndhever disse reglene er avhengig av implementering.

Heaps brukes vanligvis til å implementere prioritetskøer fordi Heap er en veldig effektiv implementering av å trekke ut det minste (eller største) elementet.

2.1. Heap Varianter

Heap har mange varianter, alle forskjellige i noen implementeringsdetaljer.

For eksempel er det vi beskrev over a Min-Heap, fordi en forelder alltid er mindre enn alle barna sine. Alternativt kunne vi ha definert Max-Heap, i så fall er en forelder alltid større enn det er barn. Derfor vil det største elementet være i rotnoden.

Vi kan velge mellom mange treimplementeringer. Det mest enkle er et binært tre. I et binært tre kan hver node maksimalt ha to barn. Vi kaller dem venstre barn og riktig barn.

Den enkleste måten å håndheve den andre regelen er å bruke et full binært tre. Et komplett binært tre følger noen enkle regler:

hvis en node bare har ett barn, bør det være det venstre barnet
bare noden lengst til høyre på det dypeste nivået kan ha nøyaktig ett barn
blader kan bare være på det dypeste nivået

La oss se disse reglene med noen eksempler:

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

Trærne 1, 2, 4, 5 og 7 følger reglene.

Tre 3 og 6 bryter den første regelen, 8 og 9 den andre regelen, og 10 bryter den tredje regelen.

I denne veiledningen, vi vil fokusere på Min-Heap med et binært tre gjennomføring.

2.2. Sette inn elementer

Vi bør implementere alle operasjoner på en måte som holder Heap-invarianter. På denne måten kan vi bygge haugen med gjentatte innsettinger, så vi fokuserer på enkeltinnsatsoperasjonen.

Vi kan sette inn et element med følgende trinn:

lag et nytt blad som er den mest tilgjengelige sporet på det dypeste nivået og lagre varen i den noden
hvis elementet er mindre enn foreldrene, bytter vi dem
fortsett med trinn 2, til elementet er mindre enn det er foreldre eller det blir den nye roten

Merk at trinn 2 ikke bryter Heap-regelen, for hvis vi erstatter en nodes verdi med en mindre, vil den fortsatt være mindre enn det er barn.

La oss se et eksempel! Vi ønsker å sette inn 4 i denne haugen:

 2 / \ / \ 3 6 / \ 5 7

Det første trinnet er å lage et nytt blad som lagrer 4:

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

Siden 4 er mindre enn foreldrene, 6, bytter vi dem:

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

Nå sjekker vi om 4 er mindre enn foreldrene eller ikke. Siden foreldrene er 2, stopper vi. Bunken er fortsatt gyldig, og vi satte inn nummer 4.

La oss sette inn 1:

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

Vi må bytte 1 og 4:

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

Nå skal vi bytte 1 og 2:

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

Siden 1 er den nye roten, stopper vi.

3. Haugimplementering i Java

Siden vi bruker en Full Binary Tree, vi kan implementere det med en matrise: et element i matrisen vil være en node i treet. Vi markerer hver node med matriseindeksene fra venstre til høyre, fra topp til bunn på følgende måte:

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

Det eneste vi trenger er å holde rede på hvor mange elementer vi lagrer i treet. På denne måten vil indeksen til det neste elementet vi vil sette inn være størrelsen på matrisen.

Ved hjelp av denne indekseringen kan vi beregne indeksen til foreldre- og barnekodene:

foreldre: (indeks - 1) / 2
venstre barn: 2 * indeks + 1
høyre barn: 2 * indeks + 2

Siden vi ikke vil bry oss med omfordeling av matriser, forenkler vi implementeringen enda mer og bruker en ArrayList.

En grunnleggende implementering av binært tre ser slik ut:

klasse BinaryTree {Listeelementer = ny ArrayList (); void add (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-indeks) {retur 2 * indeks + 1; } int rightChildIndex (int index) {return 2 * index + 2; }}

Koden ovenfor legger bare til det nye elementet i enden av treet. Derfor må vi krysse det nye elementet opp om nødvendig. Vi kan gjøre det med følgende kode:

klasse Heap {// ... ugyldig legg til (E e) {elements.add (e); int elementIndex = elements.size () - 1; mens (! isRoot (elementIndex) &&! isCorrectChild (elementIndex)) {int parentIndex = parentIndex (elementIndex); bytte (elementIndex, parentIndex); elementIndex = parentIndex; }} boolsk isRoot (int-indeks) {returindeks == 0; } boolsk isCorrectChild (int-indeks) {return isCorrect (parentIndex (index), index); } boolsk isCorrect (int parentIndex, int childIndex) {if (! isValidIndex (parentIndex) ||! isValidIndex (childIndex)) {return true; } return elementAt (parentIndex) .compareTo (elementAt (childIndex)) <0; } boolsk isValidIndex (int-indeks) {returindeks <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 at siden vi må sammenligne elementene, må de implementeres java.util. Sammenlignelig.

4. Haugsortering

Siden roten til haugen alltid inneholder det minste elementet, ideen bak Heap Sort er ganske enkel: fjern rotnoden til Heapen blir tom.

Det eneste vi trenger er en fjernoperasjon, som holder haugen i en konsistent tilstand. Vi må sørge for at vi ikke bryter strukturen til det binære treet eller Heap-eiendommen.

For å beholde strukturen kan vi ikke slette noe element, bortsett fra bladet til høyre. Så ideen er å fjerne elementet fra rotnoden og lagre det høyre bladet i rotnoden.

Men denne operasjonen vil helt sikkert bryte Heap-eiendommen. Så hvis den nye roten er større enn noen av barnets noder, bytter vi den med den minste barnetoden. Siden den minste underordnede noden er mindre enn alle andre underordnede noder, bryter den ikke Heap-eiendommen.

Vi fortsetter å bytte til elementet blir et blad, eller det er mindre enn alle barna.

La oss slette roten fra dette treet:

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

Først plasserer vi det siste bladet i roten:

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

Siden den er større enn begge barna, bytter vi den med sitt minste barn, som er 2:

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

4 er mindre enn 6, så vi stopper.

5. Implementering av haugsortering i Java

Med alt vi har ser fjerning av roten (popping) slik ut:

klasse Heap {// ... E pop () {if (isEmpty ()) {throw new IllegalStateException ("Du kan ikke poppe fra en tom haug"); } E resultat = elementAt (0); int lasElementIndex = elements.size () - 1; bytte (0, lasElementIndex); elements.remove (lasElementIndex); int elementIndex = 0; mens (! isLeaf (elementIndex) &&! isCorrectParent (elementIndex)) {int smallerChildIndex = smallerChildIndex (elementIndex); bytte (elementIndex, smallerChildIndex); elementIndex = smallerChildIndex; } returnere resultat; } boolsk isLeaf (int-indeks) {return! isValidIndex (leftChildIndex (index)); } boolsk isCorrectParent (int-indeks) {return isCorrect (indeks, leftChildIndex (indeks)) && isCorrect (indeks, rightChildIndex (indeks)); } 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 sa før, er sortering bare å lage en haug og fjerne roten gjentatte ganger:

klasse Heap {// ... statisk  List sort (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 bekrefte at det fungerer med følgende test:

@Test ugyldig gittNotEmptyIterable_whenSortCalled_thenItShouldReturnElementsInSortedList () {// gitt listeelementer = Arrays.asList (3, 5, 1, 4, 2); // når List sortedElements = Heap.sort (elementer); // deretter assertThat (sortedElements) .isEqualTo (Arrays.asList (1, 2, 3, 4, 5)); }

Noter det vi kan gi en implementering, som sorterer på plass, noe som betyr at vi gir resultatet i samme matrise som vi fikk elementene. I tillegg trenger vi ingen mellomliggende minnetildeling på denne måten. Imidlertid ville implementeringen være litt vanskeligere å forstå.

6. Tidskompleksitet

Haugsortering består av to viktige trinn, sette inn et element og fjerne rotnoden. Begge trinnene har kompleksiteten O (log n).

Siden vi gjentar begge trinnene n ganger, er den samlede sorteringskompleksiteten O (n log n).

Merk at vi ikke nevnte kostnadene for omplassering av matriser, men siden det er det På), det påvirker ikke den generelle kompleksiteten. Som vi nevnte tidligere, er det også mulig å implementere en sortering på stedet, noe som betyr at det ikke er nødvendig å omfordele matriser.

Det er også verdt å nevne at 50% av elementene er blader, og 75% av elementene er på de to nederste nivåene. Derfor tar de fleste innsettingsoperasjoner ikke mer enn to trinn.

Merk at Quicksort på virkelige data vanligvis er mer performant enn Heap Sort. Sølvfôret er at Heap Sort alltid har en verste sak O (n log n) tidskompleksitet.

7. Konklusjon

I denne opplæringen så vi en implementering av Binary Heap and Heap Sort.

Selv om det er tidskompleksitet O (n log n), i de fleste tilfeller er det ikke den beste algoritmen på virkelige data.

Som vanlig er eksemplene tilgjengelige på GitHub.

streamalism.org