kø, heaps og hashing Flashcards
Hvilken egenskaper må en binær heap oppfylle?
- Hver node v som ikke er rotnoden, er større en foreldrenoden.
- Binærtreet må være komplett.
Elementene må være samenlignbare/comparable.
Hva er et komplett binærtre?
Et tre som ‘fylles opp’ fra venstre mot høyre.
Hva er ideen bak innsetting for binære heaps?
Elementet settes alltid inn på “neste ledige plass”, altså der neste node må være for at treet fortsatt skal være komplett.
Hvis noden på den nye plassen er mindre enn foreldrenoden, så bytter de plass.
- Fortsett plassbytting rekursivt oppover i treet.
Hva er ideen bak sletting for binære heaps?
Bytt verdien i rotnoden med verdien i ‘den siste’ noden i treet (den eneste noden som kan fjernes og treet fortsatt er komplett).
Hvis noden flyttet til roten er større enn en av barna, så må den bytte plass med den minste av dem.
- Fortsett rekursivt nedover i treet.
Hvordan representeres en heap med et array?
representasjon, innsetting, sletting
Vi ønsker å representere et komplett tre som et array.
La A[0] være roten.
A[n-1] er “siste” noden i treet (vi må ha en variabel n).
Foreldrenoden til A[i] er på plass (i-1)/2
Venstre barn til A[i] er på plass 2i + 1
Høyre barn til A[i] er på plass 2i + 2
Innsetting på plass A[n] og bobbler opp om nødvendig.
Sletting ved å flytte A[n-1] til roten og bobble ned om nødvendig.
Hva er Huffman-koding?
En metode for å komprimere data, gitt en mengde symboler og en frekvens for hvert symbol.
Hvordan bygges et Huffman-tre?
Anta at vi har en prioritetskø med par av symboler og deres frekvens.
Så lenge vi har mer enn et element i køen
- Fjern de to minste nodene v1 og v2.
- Lag en ny node u der v1 og v2 er barn av u og
- u.frekvens = v1.frekvens + v2.frekvens
- Plasser u på køen.
Hva krever en god hashfunksjon og hvordan kan det implementeres?
Den må være konsistent
- Samme input gir alltid samme output.
Den må ha god distribusjon
- Ulike input bør hashe til ulike output så ofte som mulig.
Enkel funksjon:
HashString(s, N)
h = 0
for every letter c in s do
h = 31 * h + charToInt(c)
return h mod N
Hva er sparate chaining ifht. hashing?
En kollisjonshåndterings teknikk hvor vi lar hver plass i arrayet peke til en “bøtte”, hvor vi kan ta utgangspunkt i at hver bøtte er en lenket liste.
Med en lenket liste blir innsetting, oppslag og sletting relativt selvforklarende, vi operer med elementer som er tupler på formen (key, value)
- Husk at hashtabellen da er en map hvor nøkklen k som hasher til i, peker til en lenket liste om det finnes elementer for nøkkelen.
Hva er linear probing ifht. hashing?
En kollisjonshåndterings teknikk hvor vi ved kollisjon ser etter neste ledige plass i arrayet.
Hashtabell
- nøkkel k som hashes til index i
Innsetting:
- hvis A[i] er null, sett inn (k,v)
- hvis A[i] = k, sett inn (k, v)
- ellers gå til neste plass og gjenta stegene
Ved sletting må vi her passe på å tette eventuelle hull, og her har vi to strategier:
- Marker plassen som slettet.
- Søk vil ikke stoppe på markerte felter
- Ved innsetting annser vi markert felt som ledig. - Hvis hullet er på plass i, tett hullet
- Søk etter nøkkel som hasher til i eller “tidligere”
- Hvis treffer en null, kan vi avslutte
- Finner vi en slik nøkkel flyttes den (sammen med verdien) til plass i.
- Så må vi tette det nye hullet på samme måte.
- Når vi tetter hullet på plass i, leter vi fra plass i + 1 mod N frem til vi teffer et nytt hull eller finner en nøkkel som kan flyttes til plass i. Dersom vi finner en slik nøkkel, så må vi rekursivt tette hullet som oppstår når vi flytter nøkkelen til plass i.
Hva er load factor ifht. hashing?
Forholdet mellom antall elementer n i hashmappen og størrelsen på arrayet N.
Load factor er gitt ved n/N
- n delt på N
En ideell load factor ligger antagelig mellom 0.5 og 0.75.
- Altså litt mer en halvfullt array.
