Median of Stream of Integers using Heap in Java

1. Oversikt

I denne veiledningen, vi lærer å beregne medianen til en strøm av heltall.

Vi fortsetter med å angi problemet med eksempler, deretter analysere problemet og til slutt implementere flere løsninger i Java.

2. Problemstilling

Median er middelverdien av et bestilt datasett. For et sett med heltall er det like mange elementer mindre enn medianen som større.

I et bestilt sett med:

  • oddetall av heltall, midtelementet er medianen - i det bestilte settet { 5, 7, 10 }, medianen er 7
  • jevnt antall heltall, det er ikke noe midtelement; medianen beregnes som gjennomsnittet av de to midterste elementene - i det bestilte settet {5, 7, 8, 10}, medianen er (7 + 8) / 2 = 7.5

La oss anta at i stedet for et endelig sett, leser vi heltall fra en datastrøm. Vi kan definere median av en strøm av heltall som medianen av settet av heltall som er lest så langt.

La oss formalisere problemstillingen. Gitt en input av en strøm av heltall, må vi designe en klasse som utfører følgende to oppgaver for hvert heltall vi leser:

  1. Legg heltallet til settet med heltall
  2. Finn medianen til heltallene som er lest så langt

For eksempel:

legg til 5 // sortert-sett = {5}, størrelse = 1 få median -> 5 legg til 7 // sortert-sett = {5, 7}, størrelse = 2 få median -> (5 + 7) / 2 = 6 legg til 10 // sorted-set = {5, 7, 10}, size = 3 get median -> 7 add 8 // sorted-set = {5, 7, 8, 10}, size = 4 get median -> ( 7 + 8) / 2 = 7,5 .. 

Selv om strømmen er uendelig, kan vi anta at vi kan holde alle elementene i strømmen samtidig.

Vi kan representere oppgavene våre som følgende operasjoner i kode:

void add (int num); dobbel getMedian (); 

3. Naiv tilnærming

3.1. Sortert Liste

La oss begynne med en enkel idé - vi kan beregne medianen til en sortert liste av heltall ved å få tilgang til midtelementet eller de to midterste elementene i liste, etter indeks. Tidskompleksiteten til getMedian operasjonen er O (1).

Mens vi legger til et nytt heltall, må vi bestemme riktig posisjon i liste slik at liste forblir sortert. Denne operasjonen kan utføres i På) tid, hvor n er størrelsen på liste. Så, den totale kostnaden for å legge til et nytt element i liste og beregning av den nye medianen er På).

3.2. Forbedring av den naive tilnærmingen

De legge til operasjonen går i lineær tid, noe som ikke er optimal. La oss prøve å ta opp det i denne delen.

Vi kan dele opp liste i to sortert listerden mindre halvdelen av heltallene sortert i avtagende rekkefølge, og den større halvparten av heltallene i økende rekkefølge. Vi kan legge til et nytt heltall i riktig halvdel slik at størrelsen på lister avviker maksimalt med 1:

hvis elementet er mindre enn min. element av større halvdel: sett inn i mindre halvdel ved passende indeks hvis mindre halvdel er mye større enn større halvdel: fjern maks. element av mindre halvdel og sett inn i begynnelsen av større halvdel (balansere) ellers sett inn i større halvdel ved passende indeks: hvis større halvdel er mye større enn mindre halvdel: fjern min. element av større halvdel og sett inn i begynnelsen av mindre halvdel (ombalanse) 

Nå kan vi beregne medianen:

hvis lister inneholder like mange elementer: median = (maks. element av mindre halvdel + min. element av større halvdel) / 2 annet hvis mindre halvdel inneholder flere elementer: median = maks. element av mindre halvdel annet hvis større halvdel inneholder flere elementer: median = min. element av større halvdel

Selv om vi bare har forbedret tidskompleksiteten til legge til drift av noen konstant faktor, har vi gjort fremgang.

La oss analysere elementene vi får tilgang til i de to sorterte lister. Vi får potensielt tilgang til hvert element når vi skifter dem under (sortert) legge til operasjon. Enda viktigere, vi får tilgang til minimum og maksimum (ekstremum) av henholdsvis de større og mindre halvdelene legge til operasjon for ombalansering og under getMedian operasjon.

Vi kan se det ekstremer er de første elementene i deres respektive lister. Så vi må optimalisere for tilgang til elementet ved indeks 0 for hver halvdel for å forbedre den totale kjøretiden til legge til operasjon.

4. Haug-basert tilnærming

La oss avgrense vår forståelse av problemet ved å bruke det vi har lært av vår naive tilnærming:

  1. Vi må få minimum / maksimumselementet til et datasett inn O (1) tid
  2. Elementene trenger ikke holdes i en sortert rekkefølge så lenge vi kan få minimum / maksimum element effektivt
  3. Vi må finne en tilnærming for å legge til et element i datasettet vårt som koster mindre enn På) tid

Deretter ser vi på Heap-datastrukturen som hjelper oss med å nå våre mål effektivt.

4.1. Heap Datastruktur

Haug er en datastruktur som vanligvis implementeres med en matrise, men som kan betraktes som et binært tre.

Hauger er begrenset av haugegenskapen:

4.1.1. Maksheap Eiendom

En (underordnet) node kan ikke ha en verdi som er større enn foreldrenes verdi. Derfor, i en maks-haughar rotnoden alltid den største verdien.

4.1.2. Minheap Eiendom

En (foreldre) node kan ikke ha en verdi som er større enn barna sine. Dermed i en min-haughar rotnoden alltid den minste verdien.

I Java er PriorityQueue klasse representerer en haug. La oss gå videre til vår første løsning ved hjelp av dynger.

4.2. Første løsning

La oss erstatte listene i vår naive tilnærming med to dynger:

  • En min-haug som inneholder den største halvdelen av elementene, med minimumselementet ved roten
  • En maks-haug som inneholder den mindre halvdelen av elementene, med maksimalt element ved roten

Nå kan vi legge til det innkommende heltallet til den relevante halvdelen ved å sammenligne det med roten til min-haugen. Deretter, hvis størrelsen på den ene bunken etter innsetting avviker fra den andre bunken med mer enn 1, kan vi balansere dyngene på nytt, og dermed opprettholde en størrelsesforskjell på maksimalt 1:

hvis størrelse (minHeap)> størrelse (maxHeap) + 1: fjern rotelementet til minHeap, sett inn i maxHeap hvis størrelse (maxHeap)> størrelse (minHeap) + 1: fjern rotelementet til maxHeap, sett inn i minHeap

Med denne tilnærmingen kan vi beregne medianen som gjennomsnittet av rotelementene til begge haugene, hvis størrelsen på de to haugene er lik. Ellers kan den rotelementet til haugen med flere elementer er medianen.

Vi bruker PriorityQueue klasse for å representere dyngene. Standard haugegenskap for en PriorityQueue er min-haug. Vi kan lage en maks-heap ved å bruke a Comparator.reverserOrder som bruker det motsatte av den naturlige ordenen:

klasse MedianOfIntegerStream {privat kø minHeap, maxHeap; MedianOfIntegerStream () {minHeap = ny PriorityQueue (); maxHeap = ny PriorityQueue (Comparator.reverseOrder ()); } ugyldig add (int num) {if (! minHeap.isEmpty () && num minHeap.size () + 1) {minHeap.offer (maxHeap.poll ()); }} annet {minHeap.offer (num); hvis (minHeap.size ()> maxHeap.size () + 1) {maxHeap.offer (minHeap.poll ()); }}} dobbel getMedian () {int median; hvis (minHeap.size () maxHeap.size ()) {median = minHeap.peek (); } annet {median = (minHeap.peek () + maxHeap.peek ()) / 2; } retur median; }}

Før vi analyserer kjøretiden til koden vår, la oss se på tidskompleksiteten til haugoperasjonene vi har brukt:

find-min / find-max O (1) delete-min / delete-max O (log n) insert O (log n) 

getMedian operasjonen kan utføres i O (1) tid som det krever finn-min og finn-maks funksjoner bare. Tidskompleksiteten til legge til operasjonen er O (log n) - tre sett inn/slett ringer hver krever O (log n) tid.

4.3. Hvarstørrelse Invariant Løsning

I vår forrige tilnærming sammenlignet vi hvert nye element med rotelementene i dyngene. La oss utforske en annen tilnærming ved hjelp av heap der vi kan utnytte heap-eiendommen for å legge til et nytt element i riktig halvdel.

Som vi har gjort for vår forrige løsning, begynner vi med to dynger - en min-haug og en maks-haug. Deretter la oss innføre en tilstand: størrelsen på max-haugen må være (n / 2) til enhver tid, mens størrelsen på minhaugen kan være enten (n / 2) eller (n / 2) + 1, avhengig av totalt antall elementer i de to dyngene. Med andre ord kan vi bare tillate at min-haugen har et ekstra element når det totale antallet elementer er merkelig.

Med vår haugestørrelse kan vi beregne medianen som gjennomsnittet av rotelementene til begge haugene, hvis størrelsen på begge haugene er (n / 2). Ellers kan den rotelementet til min-haugen er medianen.

Når vi legger til et nytt heltall, har vi to scenarier:

1. Totalt nr. av eksisterende elementer er jevn størrelse (min-heap) == størrelse (max-heap) == (n / 2) 2. Totalt nr. av eksisterende elementer er oddestørrelse (max-heap) == (n / 2) size (min-heap) == (n / 2) + 1 

Vi kan opprettholde invarianten ved å legge det nye elementet til en av dyngene og balansere hver gang:

Ombalanseringen fungerer ved å flytte det største elementet fra maks-haugen til min-haugen, eller ved å flytte det minste elementet fra min-haugen til maks-haugen. Denne måten, skjønt vi sammenligner ikke det nye heltallet før vi legger det til en bunke, den påfølgende rebalanseringen sørger for at vi respekterer den underliggende invarianten av mindre og større halvdeler.

La oss implementere løsningen vår i Java ved hjelp av PriorityQueues:

klasse MedianOfIntegerStream {privat kø minHeap, maxHeap; MedianOfIntegerStream () {minHeap = ny PriorityQueue (); maxHeap = ny PriorityQueue (Comparator.reverseOrder ()); } ugyldig add (int num) {if (minHeap.size () == maxHeap.size ()) {maxHeap.offer (num); minHeap.offer (maxHeap.poll ()); } annet {minHeap.offer (num); maxHeap.offer (minHeap.poll ()); }} dobbel getMedian () {int median; hvis (minHeap.size ()> maxHeap.size ()) {median = minHeap.peek (); } annet {median = (minHeap.peek () + maxHeap.peek ()) / 2; } retur median; }}

Tids kompleksiteten i vår virksomhet forblir uendret: getMedian kostnader O (1) tid, mens legge til løper i tide O (log n) med nøyaktig samme antall operasjoner.

Begge de haugebaserte løsningene tilbyr lignende rom- og tidskompleksiteter. Mens den andre løsningen er smart og har en renere implementering, er tilnærmingen ikke intuitiv. På den annen side følger den første løsningen vår intuisjon naturlig, og det er lettere å resonnere om korrektheten av dens legge til operasjon.

5. Konklusjon

I denne opplæringen lærte vi hvordan vi kan beregne medianen til en strøm av heltall. Vi evaluerte noen få tilnærminger og implementerte et par forskjellige løsninger i Java ved hjelp av PriorityQueue.

Som vanlig er kildekoden for alle eksemplene tilgjengelig på GitHub.


$config[zx-auto] not found$config[zx-overlay] not found