Nada

Övning 11: Prioritetskö (heap)



Uppgift 1: Kö, stack. prioritetskö (Weiss: Ex 6.1

Om man stoppar in talen 4, 8, 1, 6 i var och en av dessa abstrakta datastrukturer, i vilken ordning kommer dom ut?

Uppgift 2: Heap

Om man stoppar in talen 4, 8, 1, 6 i den konkreta datastrukturen heap och sedan plockar ut talen, vad händer i heapens inre?

Uppgift 3: Störst i heapen

Det minsta elementet i en heap ligger som alla vet överst.
Var i heapen kan man vänta sig att det största elementet ligger?

Uppgift 4: Programdatabas

Titti Ruta vill varje vecka lägga in alla tevekanalers programtablåer i en databas för att inte missa något. Hon vill på datorns skärm hela tiden se vilka program som börjar den närmaste timmen. Vilken datastruktur vill du rekommendera?
Välj en av följande och motivera!
Vektor med binärsökning, lista med linjärsökning, binärträd, hashtabell, heap, stack.

Uppgift 5: Från fan till gud på olika sätt

Labb sju söker kortaste vägen från ett ord till ett annat genom utbyte av en bokstav i taget. Där använder man breddenförstsökning med kö - man tar ut första ordet ur kön, bildar dess söner genom utbyte av en bokstav, kollar att sonen finns i ordlistan och stoppar i så fall in den sist i kön. Eventuellt kan man ha ett binärträd för att sålla bort dumsöner (dubbletter). Vad händer om man byter kön mot en stack? Mot en prioritetskö? Vad ska man i så fall använda som prioritet?