Föreläsning 8

Question 1

Vad är en heap?

Answer 1

Två typer: min-heap, max-heap

Ett träd, där varje nod större/mindre än alla barn.

Question 2

Hur initialiseras en binary heap från en osorterad array? Vad är tidskomplexiteten?

Answer 2

1. Starta från index k=n/2 och iterera ned mot 0
2. För varje index i, jämför med element 2i, 2i+1
3. Flytta om det största elementet till i om behövs

Tidskomplexitet: O(n)

Question 3

Vad är en fibonacci heap?

Answer 3

En trädliknande datastruktur som håller reda på grannar i trädet. Detta förbättrar tiden för union operationen bland annat.