HEAPS

Question 1

Hva er en binær heap?

Answer 1

Et binært tre som oppfyller følgende egenskaper:

• Hver node v, som ikke er rotnoden, er større enn foreldrenoden.
• Binærtreet må være komplett (= fylles opp fra venstre mot høyre)

Question 2

Hva er O-notasjonen på innsetting og sletting i binære heaps?

Answer 2

O(log(n))

Question 3

Binære heaps og balanserte søketrær har samme kompleksitet, men hva er det som gjør binære heaps bedre?

Answer 3

• heaps er komplette, så de er alltid balanserte
• heaps trenger ingen rotasjoner
• De er mer balanserte enn både AVL-trær og rød-svarte trær.

Question 4

Hvor bør man forsøke å legge til en ny node i en binær heap?

Answer 4

På den neste ledige plassen.
Hvis den nye noden er mindre enn foreldrenoden, må disse bytte plass. Dette må fortsette rekursivt oppover til en node har en foreldrenode som er mindre enn seg selv

Question 5

Hvordan bør man gå frem ved sletting av en node i en binær heap?

Answer 5

Bytt verdien i rotnoden med den verdien i den “siste” noden i treet. Hvis noden er større enn en av barna, så må den bytte plass med den minste. Fortsett rekursivt.

Question 6

Binær heap: Hvilken plass ligger foreldrenoden til A[i] på?

Answer 6

På plass [(i-1)/2]

Question 7

Hvis man skal slette en node i en binær heap, hvilken slettes?

Answer 7

Den minste

Question 8

Hva er forskjellen på min-heap og max-heap?

Answer 8

Min-heap så er den minste noden rotnoden. Max-heap så er den største noden rotnoden.