Median for Stream of Integers ved hjælp af Heap i Java

1. Oversigt

I denne vejledning vi lærer at beregne medianen for en strøm af heltal.

Vi fortsætter med at angive problemet med eksempler, analyserer derefter problemet og implementerer endelig flere løsninger i Java.

2. Problemerklæring

Median er middelværdien af ​​et ordnet datasæt. For et sæt heltal er der lige så mange elementer mindre end medianen som større.

I et ordnet sæt af:

  • ulige antal heltal, det midterste element er medianen - i det bestilte sæt { 5, 7, 10 }, medianen er 7
  • lige antal heltal, der er intet mellemelement; medianen beregnes som gennemsnittet af de to midterste elementer - i det bestilte sæt {5, 7, 8, 10}, medianen er (7 + 8) / 2 = 7.5

Lad os nu antage, at vi i stedet for et begrænset sæt læser heltal fra en datastrøm. Vi kan definere median for en strøm af heltal som medianen af ​​det antal heltal, der er læst indtil videre.

Lad os formalisere problemstillingen. Givet et input af en strøm af heltal, skal vi designe en klasse, der udfører følgende to opgaver for hvert heltal, som vi læser:

  1. Føj heltal til sæt heltal
  2. Find medianen af ​​de heltal, der er læst indtil videre

For eksempel:

tilføj 5 // sorteret-sæt = {5}, størrelse = 1 få median -> 5 tilføj 7 // sorteret-sæt = {5, 7}, størrelse = 2 få median -> (5 + 7) / 2 = 6 tilføj 10 // sorteret-sæt = {5, 7, 10}, størrelse = 3 få median -> 7 tilføj 8 // sorteret-sæt = {5, 7, 8, 10}, størrelse = 4 få median -> ( 7 + 8) / 2 = 7,5 .. 

Selvom strømmen ikke er endelig, kan vi antage, at vi kan holde alle elementerne i strømmen i hukommelsen på én gang.

Vi kan repræsentere vores opgaver som følgende operationer i kode:

ugyldig tilføjelse (int num); dobbelt getMedian (); 

3. Naiv tilgang

3.1. Sorteret Liste

Lad os begynde med en simpel idé - vi kan beregne medianen af ​​en sorteret liste af heltal ved at få adgang til det midterste element eller de midterste to elementer af listeefter indeks. Tidenes kompleksitet af getMedian operation er O (1).

Mens vi tilføjer et nyt heltal, skal vi bestemme dets korrekte position i liste sådan at liste forbliver sorteret. Denne operation kan udføres i På) tid, hvor n er størrelsen på liste. Så de samlede omkostninger ved at tilføje et nyt element til liste og beregning af den nye median er På).

3.2. Forbedring af den naive tilgang

Det tilføje operation kører i lineær tid, hvilket ikke er optimalt. Lad os prøve at adressere det i dette afsnit.

Vi kan opdele liste i to sorteret listerden mindre halvdel af heltalene sorteret i faldende rækkefølge, og den største halvdel af heltalene i stigende rækkefølge. Vi kan tilføje et nyt heltal i den passende halvdel, så størrelsen på lister adskiller sig højst med 1:

hvis elementet er mindre end min. element af større halvdel: indsæt i mindre halvdel ved passende indeks, hvis mindre halvdel er meget større end større halvdel: fjern maks. element af mindre halvdel og indsæt i begyndelsen af ​​større halvdel (rebalance) ellers indsæt i større halvdel ved passende indeks: hvis større halvdel er meget større end mindre halvdel: fjern min. element af større halvdel og indsæt i begyndelsen af ​​mindre halvdel (rebalance) 

Nu kan vi beregne medianen:

hvis lister indeholder lige mange elementer: median = (maks. element af mindre halvdel + min. element af større halvdel) / 2 ellers hvis mindre halvdel indeholder flere elementer: median = maks. element af mindre halvdel, hvis større halvdel indeholder flere elementer: median = min. element af større halvdel

Selvom vi kun har forbedret tidskompleksiteten af tilføje ved hjælp af en konstant faktor, har vi gjort fremskridt.

Lad os analysere de elementer, vi har adgang til i de to sorterede lister. Vi har potentielt adgang til hvert element, når vi skifter dem under (sorteret) tilføje operation. Mere vigtigt er det, at vi får adgang til minimum og maksimum (ekstremum) af henholdsvis de større og mindre halvdele i løbet af tilføje operation til genbalancering og under getMedian operation.

Det kan vi se ekstremum er de første elementer i deres respektive lister. Så vi skal optimeres for at få adgang til elementet ved indeks 0 for hver halvdel for at forbedre den samlede driftstid for tilføje operation.

4. Bunke-baseret tilgang

Lad os forfine vores forståelse af problemet ved at anvende det, vi har lært af vores naive tilgang:

  1. Vi skal få minimum / maksimumelementet i et datasæt ind O (1) tid
  2. Elementerne behøver ikke at blive holdt i en sorteret rækkefølge så længe vi kan få minimum / maksimum element effektivt
  3. Vi er nødt til at finde en tilgang til at tilføje et element til vores datasæt, der koster mindre end På) tid

Dernæst ser vi på Heap-datastrukturen, der hjælper os med at nå vores mål effektivt.

4.1. Heap-datastruktur

Bunke er en datastruktur, der normalt implementeres med en matrix, men som kan betragtes som et binært træ.

Bunker er begrænset af bunkejendommen:

4.1.1. Maksbunkeejendom

En (underordnet) node kan ikke have en værdi, der er større end dens overordnede. Derfor i en max-bunkehar rodnoden altid den største værdi.

4.1.2. Minbunkeejendom

En (overordnet) node kan ikke have en værdi, der er større end dens børns værdi. Således i en min-bunke, rodnoden har altid den mindste værdi.

I Java er PriorityQueue klasse repræsenterer en bunke. Lad os gå videre til vores første løsning ved hjælp af dynger.

4.2. Første løsning

Lad os erstatte listerne i vores naive tilgang med to dynger:

  • En min-bunke, der indeholder den største halvdel af elementerne med minimumselementet ved roden
  • En max-heap, der indeholder den mindre halvdel af elementerne med det maksimale element ved roden

Nu kan vi tilføje det indgående heltal til den relevante halvdel ved at sammenligne det med roden af ​​min-bunken. Dernæst, hvis størrelsen på en bunke adskiller sig fra den anden bunke med mere end 1 efter indsættelse, kan vi genbalancere bunkerne og således opretholde en størrelsesforskel på højst 1:

hvis størrelse (minHeap)> størrelse (maxHeap) + 1: fjern rodelementet af minHeap, indsæt i maxHeap hvis størrelse (maxHeap)> størrelse (minHeap) + 1: fjern rodelementet af maxHeap, indsæt i minHeap

Med denne tilgang kan vi beregne medianen som gennemsnittet af rodelementerne i begge bunkerne, hvis størrelsen af ​​de to bunker er ens. Ellers er rodelementet på bunken med flere elementer er medianen.

Vi bruger PriorityQueue klasse til at repræsentere dyngene. Standardhaugegenskaben for a PriorityQueue er min-bunke. Vi kan oprette en max-heap ved hjælp af en Comparator.reverserOrder der bruger omvendt af den naturlige orden:

klasse MedianOfIntegerStream {privat kø minHeap, maxHeap; MedianOfIntegerStream () {minHeap = ny PriorityQueue (); maxHeap = ny PriorityQueue (Comparator.reverseOrder ()); } ugyldig tilføj (int num) {hvis (! minHeap.isEmpty () && num minHeap.size () + 1) {minHeap.offer (maxHeap.poll ()); }} andet {minHeap.offer (num); hvis (minHeap.size ()> maxHeap.size () + 1) {maxHeap.offer (minHeap.poll ()); }}} dobbelt getMedian () {int median; hvis (minHeap.size () maxHeap.size ()) {median = minHeap.peek (); } andet {median = (minHeap.peek () + maxHeap.peek ()) / 2; } returmedian; }}

Før vi analyserer kørselstiden for vores kode, skal vi se på tidskompleksiteten af ​​de bunkeoperationer, vi har brugt:

find-min / find-max O (1) delete-min / delete-max O (log n) indsæt O (log n) 

getMedian operation kan udføres i O (1) tid, da det kræver find-min og find-max kun funktioner. Tidenes kompleksitet af tilføje operation er O (log n) - tre indsæt/slet opkald hver kræver O (log n) tid.

4.3. Invariant opløsning af bunke størrelse

I vores tidligere tilgang sammenlignede vi hvert nye element med bunkernes rodelementer. Lad os undersøge en anden tilgang ved hjælp af bunke, hvor vi kan udnytte bunkeegenskaben til at tilføje et nyt element i den passende halvdel.

Som vi har gjort for vores tidligere løsning, begynder vi med to bunker - en min-bunke og en max-bunke. Lad os derefter introducere en betingelse: størrelsen på max-bunken skal være (n / 2) til enhver tid, mens størrelsen på min-bunken kan være enten (n / 2) eller (n / 2) + 1afhængigt af det samlede antal elementer i de to dynger. Med andre ord kan vi kun tillade min-bunken at have et ekstra element, når det samlede antal elementer er ulige.

Med vores dyngestørrelse invariant kan vi beregne medianen som gennemsnittet af rodelementerne på begge dynger, hvis størrelsen på begge dynger er (n / 2). Ellers er rodelementet i min-bunken er medianen.

Når vi tilføjer et nyt heltal, har vi to scenarier:

1. Samlet nr. af eksisterende elementer er jævn størrelse (min-bunke) == størrelse (max-bunke) == (n / 2) 2. Samlet nr. af eksisterende elementer er ulige størrelse (max-bunke) == (n / 2) størrelse (min-bunke) == (n / 2) + 1 

Vi kan opretholde invarianten ved at tilføje det nye element til en af ​​bunkerne og genbalancere hver gang:

Ombalanceringen fungerer ved at flytte det største element fra max-bunken til min-bunken eller ved at flytte det mindste element fra min-bunken til max-bunken. Denne måde dog vi sammenligner ikke det nye heltal, før vi føjer det til en bunke, den efterfølgende genbalancering sikrer, at vi ærer den underliggende invariant i mindre og større halvdele.

Lad os implementere vores løsning i Java ved hjælp af PriorityQueues:

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

Tids kompleksiteten i vores aktiviteter forbliver uændret: getMedian omkostninger O (1) tid, mens tilføje kører i tide O (log n) med nøjagtigt det samme antal operationer.

Begge de bunkebaserede løsninger tilbyder lignende rum- og tidskompleksiteter. Mens den anden løsning er smart og har en renere implementering, er fremgangsmåden ikke intuitiv. På den anden side følger den første løsning vores intuition naturligt, og det er lettere at ræsonnere om rigtigheden af ​​dens tilføje operation.

5. Konklusion

I denne vejledning lærte vi at beregne medianen af ​​en strøm af heltal. Vi vurderede et par tilgange og implementerede et par forskellige løsninger i Java ved hjælp af PriorityQueue.

Som normalt er kildekoden til alle eksemplerne tilgængelig på GitHub.