Föreläsning 6

Prioritetsköer

[kapitel 7]
OH-bilder från denna föreläsning

Finns det flera olika sorteringsalgoritmer?
Urvalssortering, bubbelsortering och insättningssortering, de "naiva" algoritmerna som inte går särskilt fort.

Hur vet man vad som är den rätta ordningen vid t.ex. sortering?
Nycklar och jämförbara objekt.
Gränssnittet Comparable.
Användning av en separat jämförare (comparator).

Vad är en prioritetskö?
En ADT som utför en begränsad sortering.
Man kan stoppa in elementen i godtycklig ordning men ändå alltid få ut dem i ordning (sorterat).

Vad är en heap?
Ett träd där elementen är delvis sorterade.

Kan en heap implementeras så att den blir snabb?
Ja! (det är liksom det som är hela poängen)
Trädet kan lagras direkt i en vektor (array).

Hur gör man insättning och borttagning i en heap?
Dessa operationer kan båda göras i O(log n)-tid, d.v.s. snabbt.